switch / if を式として

## はじめに

無職 やめ太郎（本名）氏の記事
[4歳娘「パパ、constしか使わないで？」](https://qiita.com/Yametaro/items/17f5a0434afa9b88c3b1)
のコメント欄にて、`switch` や `if` を式として構成する話が盛り上がっているようだった。
こういう話好き。

ただ、記事の主旨はタイトル通り「変数を `const` のみにするには」と言うのが主眼なようなので、コメントではなく記事にしてみることにした。

汎用的な条件分岐 (conditional branch) は Maybe と Either で構成できるよ、というお話。
若干関数型チックな雰囲気を感じるかもしれないけれど、モナモナ言い出さないので安心してほしい。

## Maybe (ある / なし)

まずは `Maybe` について。
値が「ある」場合と「ない」場合を表現する構造。
他言語だと `Optional` と呼ばれることもしばしば。
ここでは単純に、要素数が 0 または 1 の配列、と言うことにしよう。

~~~ts
type Nothing = [];
type Just<A> = [A];
type Maybe<A> = Just<A> | Nothing;
~~~

`Maybe` を扱う関数は色々考えられるけれど、ここではよく使う `maybe` 関数を導入しよう。

~~~ts
const maybe: <A, B, C>(
    m: Maybe<A>,
    f: (a: A) => B,
    v: C
) => B | C
    = (m, f, v) => '0' in m ? f(m[0]) : v;
~~~

`Maybe` `m` が値を持っていればそれに関数 `f` を適用し、そうでなければ代わりの値 `v` を返す。
使い方は以下のような感じ。

~~~ts:usage
const greet = (maybeName: Maybe<string>) =>
  'ようこそ' +
  maybe(maybeName,
    name => name + '様',
    'ゲストさん'
  );

console.log(greet(['ユーザー'])); // ようこそユーザー様
console.log(greet([])); // ようこそゲストさん
~~~

これだけでも、単純な分岐は表現できる。

## Either (どちらか一方)

`Either` は 2 種に場合分けをして、A の場合の値と B の場合の値、どちらか一方、というものを表現する構造。

~~~ts
type Left<A> = { left: A };
type Right<B> = { right: B };
type Either<A, B> = Left<A> | Right<B>;
~~~

`Left` / `Right` を構築する関数と、値を取り出して関数を適用する `either` を定義しよう。

~~~ts
const Left: <A>(left: A) => Left<A>
    = left => ({ left });
    
const Right: <B>(right: B) => Right<B>
    = right => ({ right });

const either: <A, B, X, Y>(
    e: Either<A, B>,
    f: (a: A) => X,
    g: (b: B) => Y
) => X | Y
    = (e, f, g) => 'left' in e ? f(e.left) : g(e.right);
~~~

`Either` `e` を受け取って、`Left` であれば `f` を、`Right` であれば `g` を適用する。

使い方は、例えば以下のような感じ。

~~~ts:usage
const users = [ { id: 0, name: 'A' }, { id: 1, name: 'B' } ];

const getUser = (idOrName: Either<number, string>) =>
  either(idOrName,
    id   => users.find(x => x.id === id),
    name => users.find(x => x.name === name) 
  );

console.log(getUser(Left(0))); // { id: 0, name: 'A' }
console.log(getUser(Right('B'))); // { id: 1, name: 'B' }
~~~

実際には、「計算結果」または「エラーメッセージ」など、例外処理的なものを扱うことが多い。

## Conditional Branch (条件分岐)

さて、上記 `Maybe` と `Either` を組み合わせれば、

- 入力値を受け取って
- 複数の処理に分岐し
- 出力値を返す

といった汎用的な条件分岐を構成できる。

考え方としては、

- 未分岐のものは 入力値 (`X`) を持った `Left<X>`
- 分岐済みのものは 出力値 (`Y`) をもった `Right<Y>`

として扱う、というもの。

`Either<X, Y>` が、条件分岐処理中の状態に相当する。

まず、初期状態は `Left` (未分岐)。

~~~ts
const start: <X>(input: X) => Either<X, never>
    = x => Left(x);
~~~

次に、条件分岐は `X` を受け取って `Maybe` を返す関数として表現する。
分岐した場合には `Just` を、分岐しなかった場合には `Nothing` を返す。

状態(`Either`)と条件分岐(`Maybe`を返す関数)から、次の状態を作る。

~~~ts
const branch: <X, Y, V>(
    e: Either<X, Y>,
    f: (x: X) => Maybe<V>
) => Either<X, Y | V>
    = (e, f) => either(e,
        x => maybe(f(x), y => Right(y), Left(x)),
        y => Right(y)
    );
~~~

入力となる `e` そして関数 `f` の戻り値によって 3 パターンの結果を生む。

|e | f(x) | return  |
|---|---|---|
|Left(x)  | Just(y)  | Right(y)  |
|Left(x)  | Nothing  | Left(x)  |
|Right(y)  | N/A  | Right(y)  |

最後に、条件分岐処理の終端は、`X` を受け取って値を返す関数として表現する。

状態(`Either`)と終端(値を返す関数)から、最終出力を得る。

~~~ts
const otherwise: <X, Y, V>(
    e: Either<X, Y>,
    f: (x: X) => V
) => Y | V
    = (e, f) => either(e, x => f(x), y => y);
~~~

`Either` が `Right` (既に結果がある) ならばその値、
`Left` (まだ結果が無い) ならば関数を適用した結果が戻り値となる。

この三つの関数を使って例として FizzBuzz を書いてみると以下のような感じ。

~~~ts
const fizzbuzzTest1 = (n: number) => {
    const e0 = start(n);
    const e1 = branch(e0, n => n % 15 ? [] : ['FizzBuzz']);
    const e2 = branch(e1, n => n % 3 ? [] : ['Fizz']);
    const e3 = branch(e2, n => n % 5 ? [] : ['Buzz']);
    return otherwise(e3, n => n);
};
~~~

`Either` を状態としたステートマシンだと考えても良いかもしれない。

こんな感じで汎用的な条件分岐が構成できる。

......といっても、TypeScript/JavaScript だと中間変数が必要になって明らかに書きにくいので、メソッドチェーンで書けるようにしよう。

## Match クラス

クラスとファクトリを定義する。
名前はとりあえず `Match` / `match` とした。
ついでに `otherwise` は長いので `else` にしてしまおう。

~~~ts
class Match<X, Y> {
    private constructor(private e: Either<X, Y>) { }

    static from(): Match<void, never>;
    static from<X>(x: X): Match<X, never>;
    static from<X>(x?: X) {
        return new Match(start(x));
    }

    branch<V>(f: (x: X) => Maybe<V>) {
        return new Match(branch(this.e, f));
    }

    else<V>(f: (x: X) => V) {
        return otherwise(this.e, f);
    }
}

const match = Match.from;
~~~

次のように書ける。

~~~ts
const fizzbuzzTest2 = (n: number) =>
    match(n)
        .branch(n => n % 15 ? [] : ['FizzBuzz'])
        .branch(n => n % 3 ? [] : ['Fizz'])
        .branch(n => n % 5 ? [] : ['Buzz'])
        .else(n => n);
~~~

おおよそ形にはなったけれど、三項演算子がまだ不格好なので、
`barnch` を「条件」と「結果の生成」に分離しよう。
メソッド名は `if` としてみる。

~~~ts
class Match<X, Y> {
    /* 略 */

    // 追加
    if<V>(p: (x: X) => unknown, f: (x: X) => V) {
        return this.branch(x => p(x) ? [f(x)] : []);
    }
}
~~~

これでより「らしく」なる。

~~~ts
const fizzbuzz = (n: number) =>
    match(n)
        .if(n => n % 15 === 0, _ => 'FizzBuzz')
        .if(n => n % 3 === 0, _ => 'Fizz')
        .if(n => n % 5 === 0, _ => 'Buzz')
        .else(n => n);
~~~

### Switch のようなもの

条件式に、関数ではなく入力値と比較する値を渡すものを定義しよう。
名前は `case` にする。

~~~ts
class Match<X, Y> {
    /* 略 */

    // 追加
    case<V>(p: X, f: (x: X) => V) {
        return this.branch(this.e, x => x === p ? [f(x)] : []);
    }
}
~~~

これで `switch` に似た扱いができるようになる。

~~~ts
const switchLike = (n: number) =>
    match(n)
        .case(0, _ => 'Zero')
        .case(1, _ => 'One')
        .else(_ => 'More'); // default
~~~

### If のようなもの

入力値を無視すれば普通の `if` - `else if` - `else` と同じような書き方もできる。

~~~ts
const ifLike = (value: number) =>
    match()
        .if(_ => value > 6, _ => 'High')
        .if(_ => value > 3, _ => 'Middle')
        .else(_ => 'Low');
~~~

もっとこんなユーティリティもあるよ！とか、カリー化しようぜ！とか、まあ、使う人によって色々ありそうだけれど、そこら辺はお好みでどうぞ。

## 長いおまけ (改良版)

さて、本筋としてはこれで終わりなのだけれど、上記実装はやや物足りない。

まず、素直に `Maybe` / `Either` を使って構成しているので、中間オブジェクトを色々と生成してしまっている。
コスト的に気に掛けるほどのものではないが、不要なオーバーヘッドは可能ならば省きたい所。

二点目、TypeScript 限定の話として、型ガードが効かない。

例えば以下のようなケース。

~~~ts
const isString = (x: unknown): x is string => typeof x === 'string';

const strOrNum = (x: string | number) =>
  match(x)
    .if(isString, s => 'String:' + s)
    .else(n => 'Number:' + n);
~~~

`if` 内の `s` は `string`、`else` 内の `n` は　`number` 、
と型推論してほしいところだが、残念ながら `string | number` のままである。

列挙型の漏れチェックなんかもできないので、どげんかせんといかん。

というわけで、2 点考慮して、ついでにユーティリティなども追加して書き直したのが以下。

やっていることは、

- Left / Right それぞれをクラス化, Maybe 周りはメソッド内で処理
- 型ガードが効くようにメソッドオーバーロードで受け、入力値の型から処理済みの型を除外
- 型だけ変わる部分で自分自身を返し、不要なオブジェクト生成を回避
- 他ユーティリティの追加

といった具合。

~~~ts:match.ts
type BooleanLike = unknown;
type Throwable = unknown;

export interface Match<X, Y> {
    else<V>(f: (x: X) => V): Y | V;

    branch<V>(f: (x: X) => [] | [V]): Match<X, Y | V>;

    // same as .branch(x => p(x) ? [f(x)] : [])
    if<V, T = X>(p: (x: X | T) => x is T, f: (x: T) => V): Match<Exclude<X, T>, Y | V>;
    if<V>(p: (x: X) => BooleanLike, f: (x: X) => V): Match<X, Y | V>;

    // same as .branch(x => p(x) ? [v] : [])
    ifValue<V, T = X>(p: (x: X | T) => x is T, v: V): Match<Exclude<X, T>, Y | V>;
    ifValue<V>(p: (x: X) => BooleanLike, v: V): Match<X, Y | V>;

    // same as .branch(x => x === t ? [f(x)] : [])
    case<V, T extends X = X>(t: T, f: (x: T) => V): Match<Exclude<X, T>, Y | V>;
    case<V>(t: X, f: (x: X) => V): Match<X, Y | V>;

    // same as .branch(x => x === t ? [v] : [])
    caseValue<V, T extends X = X>(t: T, v: V): Match<Exclude<X, T>, Y | V>;
    caseValue<V>(t: X, v: V): Match<X, Y | V>;

    // same as .else(x => v)
    elseValue<V>(v: V): Y | V;

    // same as .else(x => { throw newError(x) })
    throw(newError?: (x: X) => Throwable): Y;

    // same as .else(x => { throw t })
    throwValue(t: Throwable): Y;

    // covering check
    unreachable(this: Match<never, Y>): Y;
}

export function match(): Match<void, never>;
export function match<X>(x: X): Match<X, never>;
export function match<X>(x?: X): Match<X | void, never> {
    return new MatchLeft(x);
}

const left: <X, Y, T>(m: MatchLeft<X, Y>) => Match<Exclude<X, T>, Y>
    // = m => new MatchLeft(m._ as Exclude<X, T>);
    // @ts-ignore ** reinterpret cast to reduce runtime cost **
    = m => m;

const right: <X, Y>(y: Y) => Match<X, Y>
    = y => new MatchRight(y);

class MatchLeft<X, Y> implements Match<X, Y> {
    readonly _: X;

    constructor(target: X) { this._ = target; }

    // terminates

    else<V>(f: (x: X) => V) {
        return f(this._);
    }

    elseValue<V>(v: V) {
        return v;
    }

    throw(f?: (x: X) => Throwable): Y {
        throw f ? f(this._) : new Error('match error: ' + this._);
    }

    throwValue(t: Throwable): Y {
        throw t;
    }

    unreachable(): never {
        throw new Error('match error: ' + this._);
    }

    // non-terminates

    branch<V>(f: (x: X) => [] | [V]): Match<X, Y | V> {
        const r = f(this._);
        return '0' in r ? new MatchRight(r[0]) : this;
    }

    if<V, T>(p: (x: X | T) => x is T, f: (x: T) => V): Match<Exclude<X, T>, Y | V> {
        return p(this._) ? right(f(this._)) : left(this);
    }

    ifValue<V, T>(p: (x: X | T) => x is T, v: V): Match<Exclude<X, T>, Y | V> {
        return p(this._) ? right(v) : left(this);
    }

    case<V, T extends X>(t: T, f: (x: T) => V): Match<Exclude<X, T>, Y | V> {
        return this._ === t ? right(f(t)) : left(this);
    }

    caseValue<V, T extends X>(t: T, v: V): Match<Exclude<X, T>, Y | V> {
        return this._ === t ? right(v) : left(this);
    }
}

class MatchRight<X, Y> implements Match<X, Y> {
    readonly _: Y;

    constructor(result: Y) { this._ = result; }

    // terminates
    else() { return this._; }
    elseValue() { return this._; }
    throw() { return this._; }
    throwValue() { return this._; }
    unreachable() { return this._; }

    // non-terminates
    branch() { return this; }
    if() { return this; }
    ifValue() { return this; }
    case() { return this; }
    caseValue() { return this; }
}
~~~

先ほどの例もちゃんと推論できるようになる(なんでもできるわけではないが)。

~~~ts
const isString = (x: unknown): x is string => typeof x === 'string';

// OK
const strOrNum = (x: string | number) =>
  match(x)
    // Match<string | number, never>
    .if(isString, s => 'String:' + s)
    // Match<number, string>
    .else(n => 'Number:' + n);

// NG これはタイプガードであると見抜いてくれない
const strOrNum2 = (x: string | number) =>
  match(x)
    .if(x => typeof x === 'string', s => 'String:' + s)
    .else(n => 'Number:' + n);

// 一応明示すれば OK (長いが)
const strOrNum3 = (x: string | number) =>
  match(x)
    .if((x: any): x is string => typeof x === 'string',
         s => 'String:' + s)
    .else(n => 'Number:' + n);
~~~

いろいろ組み合わせた場合の挙動。

~~~ts
const isNumber = (x: unknown): x is number => typeof x === 'number';
const isString = (x: unknown): x is string => typeof x === 'string';

const getTime = (dateLike: number | string | Date): number =>
    match(dateLike)
        // Match<number | string | Date, never>
        .case('now', _ => Date.now())
        // Match<number | string | Date, number>
        .if(isString, Date.parse)
        // Match<number | Date, number>
        .if(isNumber, x => x)
        // Match<Date, number>
        .else(date => date.getTime());
~~~

漏れチェックもできるように。
`unreachable` メソッドは入力型が `never` でない時、コンパイルエラーとなる。

~~~ts
enum MyEnum {
    Hoge,
    Foo,
    Bar
}

const test1 = (x: MyEnum): string =>
    match(x)
        // Match<MyEnum, never>
        .case(MyEnum.Hoge, _ => 'Hoge')
        // Match<MyEnum.Foo | MyEnum.Bar, string>
        .case(MyEnum.Foo, _ => 'Foo')
        // Match<MyEnum.Bar, string>
        .case(MyEnum.Bar, _ => 'Bar')
        // Match<never, string>
        .unreachable(); // ok

const test2 = (x: MyEnum): string =>
    match(x)
        // Match<MyEnum, never>
        .case(MyEnum.Hoge, _ => 'Hoge')
        // Match<MyEnum.Foo | MyEnum.Bar, string>
        .case(MyEnum.Foo, _ => 'Foo')
        // Match<MyEnum.Bar, string>
        .unreachable();
        // tsc error
        // 型 'Match<MyEnum.Bar, string>' の 'this' コンテキストを
        // 型 'Match<never, string>' のメソッドの 'this' に割り当てることはできません。
        // 型 'MyEnum' を型 'never' に割り当てることはできません。
~~~

まあ、このくらいできればある程度は使い物になろう。

## おわりに

この手のもの、書いても結局パフォーマンス気にしてグルーコードくらいでしか使わない人なので、やっぱり言語サポートが欲しい。(ちゃぶ台返し)

それはそれとして、この手の話はやっぱり楽しい。