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
追記
ライブラリではモナドが複数回評価されないようメモ化しました。