JavaScript(TypeScript)でEitherモナドとMaybeモナドを作る

JavaScriptでMaybeモナドのサンプルはよくありますがEitherモナドのサンプルはあまりないのでこれを作ってみます。

この記事はTypeScript アドベントカレンダー2015 24日目の記事です。

まずはMaybeモナドで肩慣らしです。

export class Maybe<T> {
  private MAYBE: [T, void];
  constructor(private thunk_?: () => Maybe<T>) {
  }
  public bind(f: (val: T) => Maybe<T>): Maybe<T>
  public bind<U>(f: (val: T) => Maybe<U>): Maybe<U>
  public bind<U>(f: (val: T) => Maybe<U>): Maybe<U> {
    return new Maybe<U>(() => {
      const m = this.thunk_();
      switch (true) {
        case m instanceof Just: {
          return f((<Just<T>>m).extract());
        }
        case m instanceof Nothing: {
          return <Nothing>m;
        }
        case m instanceof Maybe: {
          return m.bind<U>(f);
        }
        default: {
          throw new TypeError(`Invalid monad value: ${m}`);
        }
      }
    });
  }
  public extract(): T | void
  public extract<U>(defaultValue?: U): T | U
  public extract<U>(defaultValue?: U): T | U | void {
    return this.thunk_().extract(defaultValue);
  }
}

export class Just<T> extends Maybe<T> {
  private MAYBE_JUST: T;
  constructor(private val_: T) {
    super();
  }
  public bind(f: (val: T) => Maybe<T>): Maybe<T>
  public bind<U>(f: (val: T) => Maybe<U>): Maybe<U>
  public bind<U>(f: (val: T) => Maybe<U>): any {
    return new Maybe(() => this).bind(f);
  }
  public extract(): T
  public extract<U>(defaultValue: U): T
  public extract<U>(defaultValue?: U): T {
    return this.val_;
  }
}

export class Nothing extends Maybe<any> {
  private MAYBE_NOTHING: void;
  public bind(f: (val: any) => Maybe<any>): Nothing {
    return this;
  }
  public extract(): void
  public extract<U>(defaultValue: U): U
  public extract<U>(defaultValue?: U): U {
    return defaultValue;
  }
}

import {Maybe as Maybe_, Just as Just_, Nothing as Nothing_} from './maybe-impl';

export type Maybe<T> = Maybe_<T>;
export namespace Maybe {
  export type Just<T> = Just_<T>;
  export function Just<T>(val: T): Just<T> {
    return new Just_(val);
  }
  export type Nothing = Nothing_;
  export const Nothing = new Nothing_();
  export const Return = Just;
}

export type Just<T> = Maybe.Just<T>;
export const Just = Maybe.Just;
export type Nothing = Maybe.Nothing;
export const Nothing = Maybe.Nothing;
export const Return = Just;

基本的な動作を確認をしてみます。

    it('Just', () => {
      const result = Return(0)
        .bind(n => Just(n + 1))
        .bind(n => Just(n + 1).bind(n => Just(`Just ${n}`)))
        .extract('Nothing');
      assert(result === 'Just 2');
    });

    it('Just nest', () => {
      const result = Return(Return(0))
        .bind(m => Just(m))
        .bind(m => m.bind(n => Just(n + 1)).bind(n => Just(`Just ${n}`)))
        .extract('Nothing');
      assert(result === 'Just 1');
    });

    it('Nothing', () => {
      const result = Return(0)
        .bind(n => Just(n + 1))
        .bind(n => Just(`Just ${n}`).bind(_ => Nothing))
        .bind(throwError)
        .extract('Nothing');
      assert(result === 'Nothing');
    });

    it('Nothing nest', () => {
      const result = Return(Return(0))
        .bind(m => m.bind(n => Nothing).bind(throwError))
        .bind(throwError)
        .extract('Nothing');
      assert(result === 'Nothing');
    });

モナド則を満たしているか確認します。

    it('Monad law 1', () => {
      const f = (n: number) => Return(n + 1);
      const x = 0;
      const ma = Return(x).bind(f);
      const mb = f(x);
      assert(ma.extract() === mb.extract());
    });

    it('Monad law 2', () => {
      const f = (n: number) => Return(n + 1);
      const x = 0;
      const ma = Return(x);
      const mb = ma.bind(Return);
      assert(ma.extract() === mb.extract());
    });

    it('Monad law 3', () => {
      const f = (n: number) => Return(n + 2);
      const g = (n: number) => Return(n * 3);
      const x = 1;
      const ma = Return(x)
        .bind(f)
        .bind(g);
      const mb = Return(x)
        .bind(n =>
          f(x)
            .bind(g));
      assert(ma.extract() === mb.extract());
    });

モナドであることが確認できました。

ついでに実行速度を計測しておきます。

    it('Just', function (done) {
      benchmark('Just', () => Just(0), done);
    });

    it('bind', function (done) {
      const just = Just(0);
      benchmark('bind', () => just.bind(n => Just(n)).extract(), done);
    });

Chrome 47.0.2526 (Windows 7 0.0.0) LOG: 'Maybe Just x 16,005,033 ops/sec ±4.19% (74 runs sampled)'
.
Firefox 43.0.0 (Windows 7 0.0.0) LOG: 'Maybe Just x 10,628,015 ops/sec ±7.73% (70 runs sampled)'
.
Chrome 47.0.2526 (Windows 7 0.0.0) LOG: 'Maybe bind x 2,352,541 ops/sec ±3.78% (74 runs sampled)'
.
Firefox 43.0.0 (Windows 7 0.0.0) LOG: 'Maybe bind x 2,776,510 ops/sec ±5.23% (74 runs sampled)'
.

十分な速さです。

さて、本題のEitherモナドを作ってみましょう。

export class Either<L, R> {
  private EITHER: [L, R];
  constructor(private thunk_?: () => Either<L, R>) {
  }
  public bind(f: (val: R) => Either<L, R>): Either<L, R>
  public bind<_R>(f: (val: R) => Either<L, _R>): Either<L, _R>
  public bind<_R>(f: (val: R) => Either<L, _R>): Either<L, _R> {
    return new Either<L, _R>(() => {
      const m = this.thunk_();
      switch (true) {
        case m instanceof Left: {
          return <Left<L>><any>m;
        }
        case m instanceof Right: {
          return f((<Right<R>>m).extract());
        }
        case m instanceof Either: {
          return m.bind<_R>(f);
        }
        default: {
          throw new TypeError(`Invalid monad value: ${m}`);
        }
      }
    });
  }
  public extract(): L | R
  public extract<_L>(transform: (left: L) => _L): _L | R
  public extract<_L>(transform?: (left: L) => _L): L | _L | R {
    return (<(transform: (left: L) => _L) => L | _L | R>this.thunk_().extract)(transform);
  }
}

export class Left<L> extends Either<L, any> {
  private EITHER_LEFT: L;
  constructor(private val_: L) {
    super();
  }
  public bind(f: (val: any) => Either<L, any>): Left<L> {
    return <any>this;
  }
  public extract(): L
  public extract<_L>(transform: (left: L) => _L): _L
  public extract<_L>(transform?: (left: L) => _L): L | _L {
    return transform ? transform(this.val_) : this.val_;
  }
}

export class Right<R> extends Either<any, R> {
  private EITHER_RIGHT: R;
  constructor(private val_: R) {
    super();
  }
  public bind<L>(f: (val: R) => Either<L, R>): Either<L, R>
  public bind<L, _R>(f: (val: R) => Either<L, _R>): Either<L, _R>
  public bind<L, _R>(f: (val: R) => Either<L, _R>): any {
    return new Either<L, R>(() => this).bind<_R>(f);
  }
  public extract(transform?: (left: any) => any): R {
    return this.val_;
  }
}

import {Either as Either_, Left as Left_, Right as Right_} from './either-impl';

export type Either<L, R> = Either_<L, R>;
export namespace Either {
  export type Left<L> = Left_<L>;
  export function Left<L>(val: L): Left<L> {
    return new Left_<L>(val);
  }
  export type Right<R> = Right_<R>;
  export function Right<R>(val: R): Right<R> {
    return new Right_<R>(val);
  }
  export const Return = Right;
}
export type Left<L> = Either.Left<L>;
export const Left = Either.Left;
export type Right<R> = Either.Right<R>;
export const Right = Either.Right;
export const Return = Either.Return;

基本動作

    it('Left', () => {
      const result = Return(0)
        .bind(n => Right(n + 1))
        .bind(n => Right(n + 1).bind(n => Left(`Left ${n}`)))
        .bind(n => Right(`Right ${n}`))
        .extract(l => `Left ${l}`);
      assert(result === 'Left Left 2');
    });

    it('Left nest', () => {
      const result = Return(Return(0))
        .bind(m => m.bind(n => Left(NaN)).bind(throwError))
        .bind(throwError)
        .extract(_ => 'Nothing');
      assert(result === 'Nothing');
    });

    it('Right', () => {
      const result = Return(0)
        .bind(n => Right(n + 1))
        .bind(n => Right(n + 1).bind(n => Right(`Right ${n}`)))
        .extract(l => `Left ${l}`);
      assert(result === 'Right 2');
    });

    it('Right nest', () => {
      const result = Return(Return(0))
        .bind(m => Right(m))
        .bind(m => m.bind(n => Right(n + 1)).bind(n => Right(`Right ${n}`)))
        .extract(_ => 'Nothing');
      assert(result === 'Right 1');
    });

モナド則

    it('Monad law 1', () => {
      const f = (n: number) => Return(n + 1);
      const x = 0;
      const ma = Return(x).bind(f);
      const mb = f(x);
      assert(ma.extract() === mb.extract());
    });

    it('Monad law 2', () => {
      const f = (n: number) => Return(n + 1);
      const x = 0;
      const ma = Return(x);
      const mb = ma.bind(Return);
      assert(ma.extract() === mb.extract());
    });

    it('Monad law 3', () => {
      const f = (n: number) => Return(n + 2);
      const g = (n: number) => Return(n * 3);
      const x = 1;
      const ma = Return(x)
        .bind(f)
        .bind(g);
      const mb = Return(x)
        .bind(n =>
          f(x)
            .bind(g));
      assert(ma.extract() === mb.extract());
    });

ベンチマーク

    it('Right', function (done) {
      benchmark('Right', () => Right(0), done);
    });

    it('bind', function (done) {
      const right = Right(0);
      benchmark('bind', () => right.bind(n => Right(n)).extract(), done);
    });

Chrome 47.0.2526 (Windows 7 0.0.0) LOG: 'Either Right x 19,315,144 ops/sec ±4.97% (76 runs sampled)'
.
Firefox 43.0.0 (Windows 7 0.0.0) LOG: 'Either Right x 12,051,406 ops/sec ±5.15% (77 runs sampled)'
.
Chrome 47.0.2526 (Windows 7 0.0.0) LOG: 'Either bind x 2,131,294 ops/sec ±3.88% (77 runs sampled)'
.
Firefox 43.0.0 (Windows 7 0.0.0) LOG: 'Either bind x 2,634,425 ops/sec ±5.30% (77 runs sampled)'
.

MaybeモナドもEitherモナドもJavaScriptで実用的な実装を作ることができます。

これらのモナドは以下のライブラリに含まれています。

github.com

追記

ライブラリではモナドが複数回評価されないようメモ化しました。