Henry

Blog

Read

Category Theory

Aug 25, 2022

Category Theory ¹

카테고리 이론은 Object 사이의 morphism을 정의한다. composition을 정의하기에 적합한 이론이다. 합성을 위해서는 정의역과 치역의 타입이 일치해야한다. 타입스크립트에서는 Object는 타입이고 morphism 은 함수가 된다.

/** f :: (a: A) => B */
const f = (s: string): number => s.length;
/** g :: (c: C) => D */
const g = (n: number): boolean => n > 2;

/**
* gf = g ∘ f
* gf :: (a: A) => D
* C = B
*/
const gf = (s: string): boolean => g(f(s));

function flow<A, B, C>(f: (a: A) => B, g: (b: B) => C): (a: A) => C {
    return (a) => g(f(a));
}

function pipe<A, B, C>(a: A, f: (a: A) => B, g: (b: B) => C): C
    return flow(f, g)(a);
}

Functors ²

순수함수는 가변성을 금지하고 참조투명성을 위반하지 않아야 하며 이를 위반하는 요소는 사이드 이펙트로 간주한다. 하지만 이러한 사이드 이펙트를 완전히 배제해서는 프로그램을 개발할 수 없다. 따라서 효과적으로 이펙트를 관리하기 위해 몇가지 방법을 사용하는데 펑터도 그중 하나다.

Why is finding solutions to this problem so important? Because, if it is true that categories can be used to model programming languages, morphisms (functions in the TS category) can be used to model programs. Thus, solving this abstract problem means finding a concrete way of composing programs in a generic way. And that is really interesting for us developers, isn't it?

/** 
 * 펑터는 일종의 컨테이너 다.
 * n -ary 타입 생성자로 모든 `X` 타입을 `F<X>`로 매핑한다. 
 **/
map: <A, B>(f: (a: A) => B) => ((fa: F<A>) => F<B>)

Functions as programs

함수로 프로그램을 모델링하려고 하면 바로 문제에 직면하게 된다.

사이드 이펙트를 발생시키는 순수함수를 어떻게 구현 가능한 것인가?

정답은 바로 사이드 이펙트를 의미하는 타입인 effects를 생성하여 이를 통해 사이드 이펙트를 모델링하는 것이다.


DSL

함수가 사이드 이펙트에 대한 설명을 반환하도록 공역을 변경한다.

type DSL = ... // sum type of every possible effect handled by the system
function log(message: string): DSL {
    return {
        type: "log",
        message
    }
}

THUNK

A Thunk representing a synchronous side effect

// a thunk representing a synchronous side effect
type IO<A> = () => A;

const log = (message: string): IO<void> => {
    return () => console.log(message); // returns a thunk
};

export const main = log("hello!");
// there's nothing in the output at this point
// because `main` is only an inert value
// representing the computation

main();
// only when launching the program I will see the result


Decomposition

예제에서 나온 코드를 바탕으로 일반 코드에서의 상황을 고려해보자. FP의 특성은 작은 모듈(순수함수)로 나누어 데이터에 대한 연산을 처리(일종의 SRP 처럼 동작하도록)한후 함수들을 합성하여 프로그램을 형성한다. 이러한 관점을 토대로 함수를 구현할때 문제를 분해하는 사고가 필요하다.


유저 데이터로부터 팔로워의 이름을 가져오는 코드를 작성한다고 해보자. 데이터를 파싱하기 위해 일련의 순서를 따를 수 있다.

  • 인터페이스를 통해 가져와야할 데이터의 타입을 알 수 있다.
  • 팔로워의 타입은 ReadonlyArray<T> 이며 우리가 원하는 이름은 string 이다.
  • 따라서 구현해야할 함수를 2가지로 보고 follower 데이터만을 출력하는 함수와 팔로워의 이름을 출력하는 함수를 생성한다.
  • 두 가지 함수를 구현했다면 합성을 통해 보다 표현력이 높은 코드를 작성할 수 있다.
  • 다만 여기서 타입(morphism)이 다른 함수를 합성하기 위해서 함수의 변형이 필요한데 이를 functor를 통해 해결할 수 있다.
import { flow } from 'fp-ts/function'

interface User {
    readonly id: number
    readonly name: string
    readonly followers: ReadonlyArray<User>
}
/** map :: (g: (b: T) -> U) -> (fb: F<T>) -> F<U> */
const map = <B, C>(g: (b: B) => C) => (fb: ReadonlyArray<B>): ReadonlyArray<C> => fb.map(g)

/** g :: (a: T) -> F<T> */
const get_followers = (user: User): ReadonlyArray<User> => user.followers
/** f :: (a: T) -> String */
const get_name = (user: User): string => user.name
/** T -> F<String> */
const get_followers_name = flow(get_followers, map(get_name))

const user: User = {
    id: 1,
    name: 'Ruth R. Gonzalez',
    followers: [
        { id: 2, name: 'Terry R. Emerson', followers: [] },
        { id: 3, name: 'Marsha J. Joslyn', followers: [] }
    ]
}

console.log(get_followers_name(user))  // [ 'Terry R. Emerson', 'Marsha J. Joslyn' ]


Functors and Functional error handling

함수형 프로그래밍은 에러를 발생시키보다는 값을 반환한다. 이 경우에 어떤 장점이 존재하는가?

declare const do_something_with_index: (index: number) => string

/** before applying the functor */
const program = (ns: ReadonlyArray<number>): string => {
    const i = ns.findIndex((n) => n > 0)
    if (i !== -1) return do_something_with_index(i)
    throw new Error('cannt find a positive number')
}

/** after applying the functor */
const program = (ns: ReadonlyArray<number>): Option<string> =>
    pipe(
        ns,
        findIndex((n) => n > 0),
        map(do_something_with_index)
    )


Monad

모나드는 함수형 프로그래밍에서 가장 중요한 추상화중 하나다. 모나드는 컨테이너 안으로 값을 리프팅하고 어떤 규칙을 정해 통제한다는 생각으로 자료형을 생성하는 것이다. 잘못된 입력이 넘어와도 컨테이너가 알아서 이를 처리한다.

1 f: (a: A) => F<B>
2 g: (b: B) => F<C>

Monad Definition

  1. 펑터 인스턴스를 허용하는 타입 생성자 M
  2. of: <A>(a: <A>) => M<A> 의 시그니쳐가 있는 함수
  3. chain: <A, B>(f: (a: A) => M<B>) => (ma: M<A>) => M<B> 의 시그니쳐가 있는 함수

  1. fp-ts
  2. functors