[Typescript로 보는 ADT] Functor

merong·2019년 6월 1일

fp typescript

Typescript로 보는 ADT

목록 보기

1/1

서론

이 글은 함수형 프로그래밍, 그 중에서도 타입을 이용한 함수형 프로그래밍을 다룹니다.

여러번에 걸쳐 다양한 타입을 소개하는 것을 목표로 하고있습니다.

첫 번째 주제는 간단하면서도 유용한 Functor입니다.

ADT

ADT는 Algebraic Data Type으로 함수형 프로그래밍에서 타입을 표현하는 한 가지 방식입니다.

조금 자세하게는 구조 타입(type C = { a: A, b: B })과 유니온 타입(type C = A | B)을 의미합니다.

여기에 제네릭과 몇 가지 기능을 추가해서 제공하는 것이 typescript의 타입 시스템입니다.

이 글에서는 기존의 타입과 앞으로 살펴볼 ADT 타입을 구분하기 위해 다음과 같은 작은 가정을 하겠습니다.

ADT는 불변
ADT는 생성할 때 사용한 값을 은폐하지 않습니다
ADT는 생성할 때 사용한 값 외에는 사용하지 않습니다

함수형 프로그래밍

함수형 프로그래밍은 사이드 이펙트가 없습니다 때문에 ADT를 사용할 때는 가변동작을 고려하지 않습니다.

불변은 처음에는 낯설지만, 불변이 갖는 규칙은 유용한 성질을 파생시킵니다.

타입마다의 성질을 이해하고 적재적소에 사용할 수 있다면, 불변 제약은 불편함이 아니라 없어서는 안되는 것 것 처럼 느껴질 것입니다.

Functor

Functor는 ADT입니다 Typescript에서는 Array, Record, Promise, Function 등이 Functor에 해당합니다.

이 들의 특징은 제네릭한 타입을 품을 수 있다는 것과 자신이 품고있는 값에 함수를 적용할 수 있다는 것입니다.

가장 대표적인 예시가 Array입니다 제네릭을 품을 수 있고, map이라는 메서드를 통해 원소에 함수를 적용할 수 있습니다.

불변을 가정했기 때문에 자신이 품고있는 값에 함수를 적용한다는 것은 단순히 순회하면서 호출하는 것을 의미하지 않습니다. 불변이고 사이드이펙트가 없기 때문에 호출만으로는 의미를 갖지 못합니다. 호출을 한 결과를 자신과 같은 타입(Array)로 만들어 반환하는 것을 의미합니다. (이 절차를 편의를 위해 mapping이라 부르겠습니다)

Record의 경우에는 map에 해당하는 메서드는 없지만, key는 그대로 두고 value만 mapping하는 동작은 충분히 만들 수 있기 때문에 Functor로 볼 수 있습니다.

Promise는 then이 Array의 map에 해당하는 동작이고, 함수에 대해서는 이후에 다루겠습니다.

Functor의 규칙

mapping 동작이 Functor를 정의합니다. mapping 할 수 있으면 Functor입니다.

단, mapping은 두 가지 제약을 만족시켜야합니다.

identity rule

const itentity = <T>(t: T) => t;

const functorB = map(functorA, identity);

// 만족해야 하는 제약조건
equals(functorA, functorB); // true

위의 map은 functor에 호환되는 mapping에 대한 동작이고, equals은 두 값이 같은지 비교해주는 함수입니다.

composition rule

const compose = <A, B, C>(f: (b: B) => C, g: (a: A) => B) => (a: A) => f(g(a));
function f(a: A): B;
function g(b: B): C;
const h = compose(g, f);

const functorB = map(functorA, f);
const functorC = map(functorB, g);
const functorD = map(functorA, h);

// 만족해야 하는 제약조건
equals(functorC, functorD); // true

위 규칙은 특정 조건에 따라 계산 순서를 비틀어도 결과 값은 같아야 한다는 것을 의미합니다.

Functor의 성질

Functor를 사용할 때, 좀 더 자세하게 mapping을 할 때는 identity로 mapping하면 결과가 같다는 것과, 연속된 mapping은 하나로 compose해서 mapping한 것의 결과와 같다는 성질이 보장됩니다.

이 성질은 mapping이 기존의 값을 변경하지 않기 때문에 성립할 수 있는 규칙입니다.

규칙을 깨는 방법은 조건을 어기는 것입니다. 다음과 같이 Functor를 사용한다면 위에서 소개한 성질이 사라집니다.

interface User {
  name: string;
}

function f(user: User) {
  user.name = `[${user}]`;
  return user.name;
}

function g(name: string) {
  return name.length;
}

const users: User[] = [{ name: 'oyster' }, { name: 'cucumber' }];

const resultA = users.map(f).map(g);
const resultB = users.map(user => g(f(user)));

equals(resultA, resultB); // false

코드의 표현은 다르지만 composition rule이 성립하지 않습니다. f가 user를 변경시켰기 때문입니다. 사이드 이펙트가 발생하는 코드는 ADT의 성질을 깨뜨리기 쉽습니다.

반대로, 규칙을 지키면 Functor의 성질을 사용할 수 있습니다

const inc = (n: number) => n + 1;

const xs = [0, 1, 2];

const ys = xs.map(inc).map(inc).map(inc).map(inc).map(inc).map(inc).map(inc).map(inc).map(inc).map(inc);
const zs = xs.map(x => inc(inc(inc(inc(inc(inc(inc(inc(inc(inc(x)))))))))));
equals(ys, zs); // true

const px = Promise.resolve(0);

const py = px.then(inc).then(inc).then(inc).then(inc).then(inc).then(inc).then(inc).then(inc).then(inc).then(inc);
const pz = px.then(x => inc(inc(inc(inc(inc(inc(inc(inc(inc(inc(x)))))))))));
equals(py, pz); // true

한 번의 연산을 여러번 나눠서 하거나 한 번에 접어서 하거나 결과는 같지만, 접는다면 중간에 생성되는 임시 객체를 생략할 수 있습니다.

둘의 결과는 같기 때문에 별 문제 없이 함수를 접어서 사용할 수 있습니다.

일반화된 mapping

typescript에서는 Functor를 직접 제공하고 있지 않습니다.

더 큰 문제는 제네릭보다 추상적인 타입(Higher Kinded Type)을 표현할 수단이 없어서 Functor에 대한 일반화된 함수를 표현하기 번거롭다는 것입니다. (이를 억지로 표현하는 Hack에 대해 다음에 포스팅 하겠습니다)

표현할 수단이 없기 때문에 아쉽지만 지금은 타입마다 mapping의 동작을 정의하고 이를 각자 오버로딩하는 방식으로 map 함수를 만들겠습니다. 메서드로도 심으면 좋겠지만, 내장 타입이라 직접 만지기 꺼려집니다.

Array.map과 Promise.then은 내장된 정의를 그대로 끌어와 사용합니다.

Record

Record에 대한 map은 key는 보존하면서 value에 함수를 mapping하는 동작입니다.

type RecordKey = string | number | symbol;

function mapRecord<A, B>(f: (a: A) => B, record: Record<RecordKey, A>): Record<RecordKey, B> {
  const ret: any = {};
  const pairs = Object.entries(record)
    .map(([key, value]) => [key, f(value)])
    .forEach(([key, value]) => ret[key] = value);

  return ret;
}

Function

Function에 대한 map은 어떨까요?

동작을 정의하기 앞서, Function 타입에 대한 mapping이 무엇인지 먼저 생각을 정리하겠습니다.

우선 Function에 대한 mapping이기 때문에 결과 값은 Function입니다.

mapping에 대한 동작은 품고 있는 값에 함수를 적용하는 것이고, 여기서는 Function이 품고있는 값에 적용하는 것입니다.

함수가 품고있는 값은 호출을 했을 때 드러납니다, 이 값에 함수를 적용한다는 것은 호출 후에 함수를 적용한다는 의미가 되고, 함수 합성을 의미합니다.

// 가변인자의 타입은 다음과 같이 고정할 수 있습니다
function mapFunc<A, B, R extends any[]>(f: (a: A) => B, func: (...args: R) => A) {
  return (...args: R) => f(func(...args));
}

map

준비한 네 가지 타입에 대한 모든 mapping 동작이 준비됐습니다. 이를 오버로딩으로 엮어서 일반화된 map 함수를 만듭니다.

type RecordKey = string | number | symbol;

function mapRecord<A, B>(f: (a: A) => B, record: Record<RecordKey, A>): Record<RecordKey, B> {
  const ret: any = {};
  const pairs = Object.entries(record)
    .map(([key, value]) => [key, f(value)])
    .forEach(([key, value]) => ret[key] = value);

  return ret;
}

function mapFunc<A, B, R extends any[]>(f: (a: A) => B, func: (...args: R) => A) {
  return (...args: R) => f(func(...args));
}

function map<A, B>(f: (a: A) => B, array: A[]): B[];
function map<A, B>(f: (a: A) => B, record: Record<RecordKey, A>): Record<RecordKey, B>;
function map<A, B>(f: (a: A) => B, promise: Promise<A>): Promise<B>;
function map<A, B, R extends any[]>(f: (a: A) => B, func: (...args: R) => A): (...args: R) => B;
function map<A, B>(f: (a: A) => B, functor: any) {
  const isPromise = (target: any) => Promise.resolve(target) == target;

  if (Array.isArray(functor)) {
    return functor.map(f);
  } else if (isPromise(functor)) {
    return functor.then(f);
  } else if (typeof functor === 'object') {
    return mapRecord(f, functor);
  } else if (typeof functor === 'function') {
    return mapFunc(f, functor);
  } else {
    throw new Error("Mapping Type Error");
  }
}