Zenn
🌟

TypeScriptでIMappable(Functor)

2021/09/05に公開2件
TypeScript
monad
functor
applicative
category
tech

本記事について

IMappableというインターフェースを定義することを動機として
型レベル関数という概念を導入します。

後半では型レベル関数を用いてApplicativeやMonadに相当するインターフェースの定義や、
2引数以上の型レベル関数の定義を行ってその実用可能性を示します。

IMappable導入の動機と障害

次の2つの関数を考えます。

const mapArray: <A, B>(f: (a: A) => B) => (fa: A[]) => B[] =
  (f) => (fa) =>
    fa.map(f);

const mapPromise: <A, B>(f: (a: A) => B) => (fa: Promise<A>) => Promise<B> =
  (f) => (fa) =>
    fa.then((a) => Promise.resolve(f(a))); // あるいは単にfa.then(f);でも可

型だけ取り出して並べます。
このとき、配列T[]を敢えてArray<T>と記述します。
※先ほど実装したmapArrayと名前を変えるために、名前の最後に_を付けています。

declare const mapArray_  : <A, B>(f: (a: A) => B) => (fa: Array  <A>) => Array  <B>;
declare const mapPromise_: <A, B>(f: (a: A) => B) => (fa: Promise<A>) => Promise<B>;

ArrayとPromiseの違いだけであることが分かります。
それをFとおくことで違いを吸収できそうです。

// 疑似コード
declare const mapF_: <A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>;

これを実用する上では、そのような型を持つ関数をインターフェースに定めて使います。

// 疑似コード
interface IMappable<F> {
  map: <A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>;
}

しかし、実際にはこのコードはコンパイルできません。
というのも、F<型>という記法がTypeScriptで許可されていないからです。
したがって、ジェネリクスを使わずに同様の表現をする必要があります。

型レベル関数による解決

type numbers = Array<number>;

上記のコードで、numberは型、numbersも型です。
ここで発想の転換をすると、Arrayは型を1つ受け取って、新しい型を返すと見なせます。

表記を変えてみましょう。

declare type X = number;
type Y = Array<X>;

Arrayは型Xを受け取って型Yを返すような関数に見えてきます[1]。

これを型レベル関数と呼ぶことにし、記事中ではArray<_>などのようにアンダースコアを用いて表す[2]こととします。

型レベル関数Array<_>に型Xが与えられると、それに合わせて型Array<X>が返されます。
これはインターフェースで表現することができます。

interface ArrayTypeLevelFunction {
  X: unknown;
  Y: Array<this["X"]>;
}

型Xを指定するには交差型&を利用します。

type ArrayOfStringTLF = ArrayTypeLevelFunction & { X: string };

型Yを取り出してみましょう。

type strings = ArrayOfStringTLF["Y"]; // string[]

ここで重要なのは、これまでジェネリクスを用いて実現してきたことを、
ジェネリクスを使わずに再現できている[3]ということです。

型レベル関数の定義

先ほどはArrayに特化した型レベル関数を定義しました。
これを一般化し、インターフェースとして表現します。

interface TLF {
  X: unknown;
  Y: unknown;
}

このインターフェースを継承する形で型レベル関数Array<_>を再実装します。

interface ArrayTLF extends TLF {
  Y: Array<this["X"]>;
}

型レベル関数TLFへの関数適用(application)を行うためのヘルパーを用意します。

// Type Level Function Application
type TLFA<F extends TLF, X> = (F & { X: X })["Y"];

これにより、以下のように使えます。

type booleans = TLFA<ArrayTLF, boolean>; // boolean[]

（練習問題）
型レベル関数PromiseTLFを定義し、numberを適用してPromise<number>を得てください。

解答例`PromiseTLF`
interface PromiseTLF extends TLF {
  Y: Promise<this["X"]>;
}

type PromiseOfNumber = TLFA<PromiseTLF, number>;

IMappableの定義

ここで、IMappableインターフェースを再掲します。

// 疑似コード
interface IMappable<F> {
  map: <A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>;
}

これはコンパイルできませんが、F<A>の部分をTLFA<F, A>に書き換えることで
同様のことを達成できるはずです。やってみましょう。

interface IMappable<F extends TLF> {
  map: <A, B>(f: (a: A) => B) => (fa: TLFA<F, A>) => TLFA<F, B>;
}

試しにIMappable<ArrayTLF>を実装してみます。

const arrayMappable: IMappable<ArrayTLF> = { map: (f) => (fa) => fa.map(f) };

（練習問題）
同様にpromiseMappable: IMappable<PromiseTLF>を実装してください。
map関数の実装には前述のmapPromiseを利用します。

`promiseMappable`
const promiseMappable: IMappable<PromiseTLF> = { map: mapPromise };

IMappableは型が合っていることだけを要求するので、
例えば次のように、引数を無視して常に空の配列[]を返すマッパーを定義することができます。

const uselessArrayMappable: IMappable<ArrayTLF> = { map: (f) => (fa) => [] };

これ以外にも様々なマッパーを定義することができるでしょう。

（練習問題）
次の記事を参考にMaybe<T>を定義し、それに対して型レベル関数MaybeTLFを定義しましょう。
更に、IMappable<MaybeTLF>のインスタンスを実装してください。
関数mapはその記事中のmapMaybe相当の処理を行うとします。

https://zenn.dev/eagle/articles/ts-maybe-introduction

インターフェース化による恩恵

IMappableインターフェースに対するヘルパー関数を作成してみます。

// 関数mapをアンカリー化する
const mapUncurried =
  <F extends TLF>({ map }: IMappable<F>) =>
  <A, B>(f: (a: A) => B, fa: TLFA<F, A>) =>
    map(f)(fa);

// 関数mapの引数f, faの順番を逆にする
const mapFlipped =
  <F extends TLF>({ map }: IMappable<F>) =>
  <A, B>(fa: TLFA<F, A>) =>
  (f: (a: A) => B) =>
    map(f)(fa);

// flipの一般化
const flap: <F extends TLF>(
  mappable: IMappable<F>,
) => <A, B>(ff: TLFA<F, (a: A) => B>) => (a: A) => TLFA<F, B> =
  (mappable) => (ff) => (a) =>
    mapFlipped(mappable)(ff)((f) => f(a));

これにより、個別の型に対する実装の手間を削減することができます。

（チャレンジ問題）
以下のようにIMonadLikeインターフェースを定義します。

interface IApplyable<F extends TLF> extends IMappable<F> {
  apply: <A, B>(ff: TLFA<F, (a: A) => B>) => (fa: TLFA<F, A>) => TLFA<F, B>;
}

interface IBindable<M extends TLF> {
  bind: <A, B>(ma: TLFA<M, A>) => (f: (a: A) => TLFA<M, B>) => TLFA<M, B>;
}

interface IApplicativeLike<F extends TLF> extends IApplyable<F> {
  pure: <A>(a: A) => TLFA<F, A>;
}

interface IMonadLike<M extends TLF> extends IApplicativeLike<M>, IBindable<M> {}

次のようなfromPureAndBind静的メソッドを持つクラスMonadLikeの実装を完成させてください。

class MonadLike<M extends TLF> implements IMonadLike<M> {
  constructor(
    readonly pure: <A>(a: A) => TLFA<M, A>,
    readonly bind: <A, B>(
      ma: TLFA<M, A>,
    ) => (f: (a: A) => TLFA<M, B>) => TLFA<M, B>,
    readonly apply: <A, B>(
      ff: TLFA<M, (a: A) => B>,
    ) => (fa: TLFA<M, A>) => TLFA<M, B>,
    readonly map: <A, B>(f: (a: A) => B) => (fa: TLFA<M, A>) => TLFA<M, B>,
  ) {}

  static fromPureAndBind<M extends TLF>(
    pure: <A>(a: A) => TLFA<M, A>,
    bind: <A, B>(ma: TLFA<M, A>) => (f: (a: A) => TLFA<M, B>) => TLFA<M, B>,
  ): MonadLike<M> {
    // pureとbindの2つの関数を用いて、mapとapplyを実装します
    return new MonadLike(pure, bind, /* TODO: 実装 */);
  }
}

2引数型レベル関数導入の動機と障害

通常の1引数の関数の型は、引数の型Aと返り値の型Bで表すことができます。

type Fun<A, B> = (a: A) => B;

これの型レベル関数FunTLFを表す方法を考えてみます。

最もシンプルな方法は、2つの型をとる型レベル関数を新たに定義することです。

interface TLF2 {
  X1: unknown;
  X2: unknown;
  Y: unknown;
}

欠点は1つの型をとる型レベル関数TLFとの互換性が無くなってしまうことです。

型レベル関数のカリー化

そこで、型Aを固定することで1引数の型レベル関数に還元します。

interface FunFromTLF<A> extends TLF {
  Y: Fun<A, this["X"]>; // (a: A) => this["X"]
}

これにより、以下のように使えます。

type FunFromStringTLF = FunFromTLF<string>;
type StringToNumber1 = TLFA<FunFromStringTLF, number>; // (a: string) => number

任意の型Xに対してIMappable<FunFromTLF<A>>を実装できます。

const createFunFromMappable: <X>() => IMappable<FunFromTLF<X>> = () => ({
  map: (f) => (fa) => (x) => f(fa(x)),
});

（練習問題）
IMappable<FunFromTLF<X>>中のmap関数の型を記述してください。
例えば、map<A, B>として、最初の引数fの型は(a: A) => Bとなります。
ただし、Fun<A, B>は関数(a: A) => Bに展開して記述してください。

（解答例）
f         : (a: A) => B
fa        : Fun<X, A> // (x: X) => A
map(f)(fa): Fun<X, B> // (x: X) => B
map       : (f: (a: A) => B) => (fa: (x: X) => A) => (x: X) => B

ご覧の通り、正体はただの関数の合成となります。

さて、FunFromTLF<A>自体も型レベル関数化してみましょう。

interface FunTLF extends TLF {
  Y: FunFromTLF<this["X"]>;
}

これにより、以下のように使えます。

type FunFromStringTLF_ = TLFA<FunTLF, string>;
type StringToNumber2 = TLFA<FunFromStringTLF_, number>; // (a: string) => number

これを一息に書いてみましょう。

// FunTLFに型レベル引数をstring, numberの順に与える
type StringToNumber3 = TLFA<TLFA<FunTLF, string>, number>; // (a: string) => number

FunTLFは2引数の型レベル関数と見なせます。
そこで、関数適用のヘルパーを作成します。

type TLFA2<F extends TLF, A, B> = TLFA<F, A> extends TLF
  ? TLFA<TLFA<F, A>, B>
  : never;

これにより、以下のように使えます。

type StringToNumber4 = TLFA2<FunTLF, string, number>; // (a: string) => number

部分適用もできます。

const createFunFromMappable2: <X>() => IMappable<TLFA<FunTLF, X>> = () => ({
  map: (f) => (fa) => (x) => f(fa(x)),
});

（練習問題）
2引数のカリー化された関数f: (t: T) => (a: A) => Bを考えます。
これの引数の順番を入れ替える関数flip_を定義します。

const flip_: <T, A, B>
             (f: (t: T) => (a: A) => B)
              => (a: A) => (t: T) => B =
  (f) => (a) => (t) =>
    f(t)(a);

IMappableのところで前述したflapが今定義したflipの一般化になっていることを確かめてください。

（解答例）`flip`
const flip: <T, A, B>
            (f: (t: T) => (a: A) => B)
             => (a: A) => (t: T) => B =
  <T, A, B>(f: (t: T) => (a: A) => B) => flap(createFunFromMappable<T>())(f);

（チャレンジ問題）
次のようにEither<L, R>を定義し、Either<_, _>を型レベル関数化してみてください。

type Either<L, R> =
  | { type: "Left", value: L }
  | { type: "Right", value: R }

関数合成の一般化

FunTLFを用いて関数合成の一般化ができます。
IComposableインタフェース[4]を定義します。

interface IComposable<C extends TLF> {
  compose: <T1, T2, T3>(f: TLFA2<C, T2, T3>) => (g: TLFA2<C, T1, T2>) => TLFA2<C, T1, T3>
}

以下のように実装できます。

const functionComposable: IComposable<FunTLF> = {
  compose: <A, B, C>(f: (b: B) => C) => (g: (a: A) => B) => (a: A) => f(g(a)),
}

圏

IComposable<C>にid関数を追加したインターフェースICategoryLike<C>を定義します。

interface ICategoryLike<C extends TLF> extends IComposable<C> {
  id: <A>(a: A) => A
}

先ほどのfunctionComposableを利用して、関数のICategoryLikeを作成します。

const functionCategoryLike: ICategoryLike<FunTLF> = {
  ...functionComposable,
  id: <A>(a: A) => a,
};

プログラミングの文脈では、ICategoryLike<C>のうち、
どのような純粋[5]関数f, g, hに対しても
compose(compose(h, g), f)とcompose(h, compose(g, f))が同じ挙動[6]になり、
どのような純粋関数fに対してもcompose(id, f)とcompose(f, id)とfが同じ挙動になるように
idとcomposeが実装されているとき、これらを圏Categoryと呼ぶことがあります。

functionCategoryLikeが持つcompose関数とid関数は
これらの法則を満たすという意味で重要です。

（練習問題）
関数f, g, hの型をそれぞれ次のようにおきます。

// 疑似コード
f: (a: A) => B
g: (b: B) => C
h: (c: C) => D

このとき、関数compose(compose(h, g), f)の型を書いてください。
また、compose(h, compose(g, f))の型も書き、少なくとも型は一致する[7]ことを確認してください。

（解答例）関数合成の結合則
// 疑似コード
hg = compose(h, g): (b: B) /* => C */ => D
gf = compose(g, f): (a: A) /* => B */ => C
compose(hg, f): (a: A) /* => B */ => D
compose(h, gf): (a: A) /* => C */ => D
// 以上によりどちらも型(a: A) => D

（練習問題）
同様に、compose(id, f)とcompose(f, id)とfに関して、
少なくとも型は一致することを確認してください。

（解答例）恒等関数は単位元
// 疑似コード
f: (a: A) => B
compose(id, f): (a: A) /* => B */ => B
compose(f, id): (a: A) /* => A */ => B
// 以上によりどれも型(a: A) => B

（練習問題）
functionCategoryLikeの
compose(compose(h, g), f)とcompose(h, compose(g, f))が
異なる挙動をするような関数f, g, hを挙げてください。

関手

プログラミングの文脈では、既に定義したIMappable<F>のうち、
map(id)とidが同じ挙動となり、
どのような純粋関数f, gに対しても
map(compose(g, f))とcompose(map(g), map(f))が同じ挙動となるとき、
これらを関手Functorと呼ぶことがあります。

（練習問題）
関数f, gの型をそれぞれ次のようにおきます。

// 疑似コード
f: (a: A) => B
g: (b: B) => C

このとき、関数map(compose(g, f))の型を書いてください。
また、compose(map(g), map(f))の型も書き、少なくとも型は一致することを確認してください。

（解答例）
// 疑似コード
gf = compose(g, f): (a: A) /* => B */ => C
mf = map(f)       : (fa: F<A>) => F<B>
mg = map(g)       : (fb: F<B>) => F<C>
map(gf): (fa: F<A>) => F<C>
compose(mg, mf) => (fa: F<A>) /* => F<B> */ => F<C>

（練習問題）
前に定義したuselessArrayMappableはFunctorとは呼べないことを確かめてください。

const uselessArrayMappable: IMappable<ArrayTLF> = { map: (f) => (fa) => [] };

自然変換

任意の型Aについて、F<A>からG<A>への関数を定めます。

type NaturalTransformationLike<F extends TLF, G extends TLF> =
  <A>(fa: TLFA<F, A>) => TLFA<G, A>;

NaturalTransformationLike<F, G>のFとGに対して
IMappable<F>とIMappable<G>が定義されており、そのどちらもが関手であるとします。
任意の関数f: (a: A) => Bと、関数eta: NaturalTransformationLike<F, G>について
compose(eta, mappableF.map(f))とcompose(mappableG.map(f), eta)が
同じ挙動をするとき、これを自然変換と言います。

// 疑似コード
              f : ( a:   A ) =>   B
mappableF.map(f): (fa: F<A>) => F<B>
mappableG.map(f): (ga: G<A>) => G<B>
compose(eta, mappableF.map(f)): (fa: F<A>) /* => F<B> */ => G<B>
compose(mappableG.map(f), eta): (fa: F<A>) /* => G<A> */ => G<B>

（練習問題）
Maybe<T>は型Tの値がある または ない のどちらかを表します。
言い換えると、型Tの値を0～1個持つということになります。
配列T[]は型Tの値を0個以上持つ値の型なので、Maybe<T>の値はT[]としても表すことができるはずです。

そこで、Maybe<_>からArray<_>へ変換するための関数を実装してください。

declare const maybeToArray: NaturalTransformationLike<MaybeTLF, ArrayTLF>;
（解答例）`maybeToArray`
const maybeToList: NaturalTransformationLike<MaybeTLF, ArrayTLF> = (fa) =>
  match(fa, {
    Just: ({ value }) => [value],
    Nothing: (_) => [],
  });

まとめ

TypeScript上で自己関手を表現するために、型レベル関数を導入し、
これを用いてIMappable<F>インターフェースを作成しました。

もし本記事が参考になりましたら、いいねあるいはコメントよろしくお願いします。
（あるいは正しくない記述等ありましたらコメントにてご指摘ください。）

脚注

  1. ArrayをFと読み替えるとtype Y = F<X>となり、これはy = f(x)にそっくりです。 ↩︎

  2. TypeScriptのコード上では、通常のArrayと型レベル関数Array<_>を区別したいからです。
    また、型レベル関数Array<_>と単なる型Array<X>を区別することにも繋がります。 ↩︎

  3. つまり、F<SomeType>と書く代わりに(F & { X: SomeType })["Y"]と書くことで
    ジェネリクスを疑似的に再現できるということです。 ↩︎

  4. PureScriptではSemigroupoidという名前がついています。訳すとすれば「半亜群」でしょうか。 ↩︎

  5. 同じ引数に対して常に同じ値を返し、副作用を伴わないような関数は「純粋関数」と呼ばれます。 ↩︎

  6. 2つの関数が「同じ」であるとは何か？という問いは難しいので深入りを避けますが、直観的には実行したときに同じように動作するということです。 ↩︎

  7. これは挙動が一致するための必要条件です。型だけではなく挙動（つまり実行した場合の処理）も一致していてほしいわけです。 ↩︎

GitHubで編集を提案

Discussion

miyamonzmiyamonz

面白い記事をありがとうございます！
ジェネリクスを用いない型レベル関数というものがTSでできると思っていなかったので驚きました。
質問なのですが、これに関する他の参考元の資料などはありますか？検索してもそれらしいものが見つけられませんでした。それとも筆者自身が見つけた方法でしょうか？

eagleeagle

コメントありがとうございます。
先行事例としてはインターフェースのマージを用いて高階型を疑似的に再現しているfp-tsというライブラリがあります。
ここから着想を得て、記事中で行っているような交差型&を用いた型レベル関数の実装を考えてみました。