Product and CoProduct

참고 : https://bartoszmilewski.com/2015/01/07/products-and-coproducts/

 

범주에서 특정 개체를 선택하려면 

다른 개체(및 자체)와의 관계 패턴을 설명해야만 

이 작업을 수행할 수 있다.

이러한 관계는 모피즘에 의해 정의된다.

 

범주 이론에는 대상을 관계 측면에서 정의하기 위한

Common Construction 이라고 하는 Universal Construction 이 있다. 

이를 수행하는 한 가지 방법은 개체와 모피즘으로 구성된 특정 모양인 패턴을 선택하고 

범주에서 모든 항목을 찾는 것이다. 

이러한 항목 사이에 우선 순위를 설정하고 가장 적합한 것을 선택 하는 것이다. 

 

이 과정은 우리가 웹 검색을 하는 방식을 연상시킨다. 

쿼리를 던지고 나온 결과에서 몇몇을 선택 하거나

쿼리를 조금더 구체화 하여 정밀도를 높이거나 하는 행동

검색엔진은 조회수에 따라 순위를 설정하므로 위에 예시와 비슷하다. 

 

Initial Object

Intial Object 를 다른 모든 객체로 가는 화살표가 있는 객체로 정의해보자

그러한 객체가 존재한다는 보장은 없다. 더 큰 문제는 너무 많을수 있다는 것이다.

 

해결책은 범주에서 찾을수 있다.

 

범주는 두 개체 사이에 최대 하나의 화살표를 허용한다. 

다른 개체보다 작거나 같을 수 있는 방법은 한 가지뿐이다.

이는 Intial Object 에 대한 다음 정의로 이어진다.

 

Intial Object 는 범주의 객체로 가는 단 하나의 arrow (morphism) 를 갖는 객체이다.

 

 

 

집합과 함수의 Category 에서 초기 객체는 empty set 이다.

Haskell 에서는 Void 에 해당

Void 에서 다른 type 으로의  Unique polymorphic function (고유 다형성 함수) 을 absurd 라고 부른다.

absurd :: Void -> a

 

Terminal Object

Category 의 여러 개체에서  오는 arrow(morphism) 를 받는 단 하나의 개체

 

 

객체 자체에서 다른 것으로 고유 함수(Unique Function)가 있는 경우 객체는 Intial Object 이다.

다른 것에서 객체 자체로 고유 함수(Unique Function)가 있는 경우 Terminal Object (Final Object)이다.

 

예)

Partial Ordered Set (Poset)

Initial Object 는 가장 작은 요소.

Teminal Object 는 가장 큰 요소.

 

Initial Object가 없는 경우도 있다. (모든정수의 집합)

Terminal Object 는 집합 범주에서 Singleton 이다.

(singleton 은 C++ 에서  void, Haskell 에서 unit  () )

 

우리는 unit 이 모든 유형에서 단위 유형에 이르는 단 하나의 순수 함수가 있음을 확인했다.

unit :: a -> ()
unit _ = ()

따라서 이것은 Terminal 개체의 조건이 충족된다. (여러개체에서 오는 Morphism (arrow) 을 받는 단 하나의 개체)

 

하지만 Bool 같은 경우는 이것을 충족하지 못한다. 

bool 은 두개의 경우가 있다. (True, False)

yes :: a -> Bool
yes _ = True

no :: a -> Bool
no _ = False

 

Duality (이중성)

Initial Object 와 Terminal Object 는 정의한 방식 사이에 대칭성이 있다. 

둘 사이의 차이점은 Mophism 의 방향이다.

즉 모든 구성 (Construction) 에는 그 반대가 있다. 

 

즉 Terminal Object 는 Initial Object 의 반대개체이다.

 

 

Isomorphisms

프로그래머로서 두 객체가 같다 라는 의미는 간단한 작업이 아니다. 

생각하기에 따라서 의미가 달라지기 때문이다. 

메모리에서의 동일 위치를 말할 수도 있고, 모든 요소(member) 의 값이 동일하다는 의미 인지

어쨌든 equality 를 표현하는 것은 쉽지 않은 일이다. 

 

그래서 가장 좋은 방법은 동일하게 보인다는 것으로 정의하는 것이다. 

이는 한 개체의 모든 요소가 다른 개체에 일 대 일 매핑됨을 의미한다. 

 

두개의 초기 객체 i1 과 i2 를 아래와 같이 정의해보자

이 diagram 에서 모든 모피즘은 고유하다.

위와 같이 정의되어 있을때 두개의 초기객체는 동형(Isomorphic) 이다.

원칙적으로 두 객체 사이에는 둘 이상의 동형이 있을수 있지만 여기서는 그렇지 않다. 

이 "유일한 동형에 대한 고유성"은 모든 보편적 구조(universal constructions)의 중요한 속성이다.

 

Products

product (곱) .. 일반적으로 두 집합의 데카르트 곱을 생각하면 된다.

pair (쌍) 으로 이루어진 집합니다. 

 

각 요소를 first (fst) 와 second (snd) 로 pair 의 구성요소를 선택한다고 해보자

fst :: (a, b) -> a
fst (x, y) = x
snd :: (a, b) -> b
snd (x, y) = y

이것을 그림으로 표현하면 아래와 같다.

 

p 가 fst 에 대응된다고 생각하면

q 는 snd 대응될 것이다. 

 

그런데 이러한 것을 만족하는 c 라는 객체가 여러개 일 수 있다. 

우리는 이럴경우 우선순위를 정하여 가장 우선순위가 높은것을 고른다.

 

c' 에서 c 로의 모피즘 m 이 있는경우 c가 c' 보다 더 낫다(우선순위가 높음) 라고 표현하고 싶다.

또한 p와 q 과 p' 과 q' 보다 더 나은 또는 더 보편적 이기를 원한다. 

 

fst 와 snd 가 p 와 q 보다 나음을 증명해 보자

일단 m 을 아래와 같이 정의한다면

m :: Int -> (Int, Bool)
m x = (x, True)

Bool 값이 True 인것을 확인하자

p 와 q 는 아래와 같이 구성가능 하다

p x = fst (m x) = x
q x = snd (m x) = True

 

q  는 항상 True 를 return 하게 된다. 하지만 snd 는 False 인 경우도 있다.

즉 q 를 통해 snd 를재 구성 할 수 없다. 

 

그렇기 때문에  우리는 fst 와 snd 가 더 보편적 (우선순위가 높은)  이라고 말할 수 있다. 

 

두 객체 a와 b의 product(곱)은 두 개의 투영(projection)을 갖춘 객체 c이므로 

두 개의 투영(projection)이 있는 다른 객체 c'에 대해 

c'에서 c까지의 고유한 형태 m이 있으므로 이러한 투영(projection)을 인수분해한다. 

 

이러한 product 는 type 으로 생각했을때 일반적으로 Tuple (pair) 을 의미한다. 

 

 

Coproduct

범주 이론에 의하면 이중성이 존재하므로 product 도 coproduct 가 존재한다. 

product 패턴에서 화살표를 반대로 하면 아래와 같은 그림이 된다. 

 

i :: a -> c
j :: b -> c

product 과 마찬가지고 우선순위(더 나은것)를 정할 수 있다. 

 

i' = m . i
j' = m . j

 

프로그래밍의 관점에서  union 을 의미한다고 할 수 있다. 

variant (typescript 에서는 union type 이 있다.)

 

A 또는 B 일 수 있는 type 을 말하며 일반적으로 Either 라고 지칭한다.

 

Haskell 에서는 다음과 같이 정의한다. 

Either a b = Left a | Right b

 

 

Coproduct (Sum type) 에 해당하는 Either 를 C# 으로 구현해 보자

public interface IEither<L, R>
{
    T Match<T>(Func<L, T> onLeft, Func<R, T> onRight);
}
public class Left<L, R> : IEither<L, R>
{
    private readonly L left;

    public Left(L left)
    {
        this.left = left;
    }

    public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight)
    {
        return onLeft(left);
    }
}

public class Right<L, R> : IEither<L, R>
{
    private readonly R right;

    public Right(R right)
    {
        this.right = right;
    }

    public T Match<T>(Func<L, T> onLeft, Func<R, T> onRight)
    {
        return onRight(right);
    }
}

var onLeft = (string s) => s.Length % 2 == 0;
var onRight = (int i) => i % 2 == 0;

IEither<string, int> e = new Right<string, int>(42);
WriteLine(e.Match(onLeft, onRight));

e = new Left<string, int>("foo");
WriteLine(e.Match(onLeft, onRight));

///
True
False

 

정상응답과 Error 응답으로 나누어서 Error 를 처리 하는 경우도 있다.

public enum VoteError
{
    Empty = 0,
    Tie
}

private IEither<VoteError, T> FindWinner<T>(IReadOnlyCollection<T> votes)
{
    var countedVotes = from v in votes
                       group v by v into g
                       let count = g.Count()
                       orderby count descending
                       select new { Vote = g.Key, Count = count };
    var c = countedVotes.Take(2).Count();

    if (c == 0)
        return new Left<VoteError, T>(VoteError.Empty);

    var x0 = countedVotes.ElementAt(0);
    if (c == 1)
        return new Right<VoteError, T>(x0.Vote);

    var x1 = countedVotes.ElementAt(1);
    if (Equals(x0.Count, x1.Count))
        return new Left<VoteError, T>(VoteError.Tie);

    return new Right<VoteError, T>(x0.Vote);
}

private IEither<VoteError, T> FindWinner<T>(params T[] votes)
{
    return FindWinner((IReadOnlyCollection<T>)votes);
}

...
...
// 실행
var matchLeft = (VoteError ve) => ve.ToString();
var matchRight = (string s) => s;

WriteLine(FindWinner(new string[0] { }).Match(matchLeft, matchRight));
WriteLine(FindWinner(new [] { "Foo"}).Match(matchLeft, matchRight));
WriteLine(FindWinner(new[] { "Foo","Bar" }).Match(matchLeft, matchRight));
///
Empty
Foo
Tie

 

관련영상

https://youtu.be/_NSIUQQ-cL4