「関数型プログラミングの基礎」代数的データ構造とパターンマッチを理解する

この本で関数型プログラミングの基礎を押さえようとしたけれど、p140の「代数的データ構造とパターンマッチ」あたりから理解に苦しんだのでメモをとりながらじっくり進めることにした。
全てのコードはここに置いてある。
akimichi.github.io

JavaScriptのswitch文では、配列のように可変なデータの場合にはアドレス値で比較されるので、マッチングは失敗する。
以下が良い例である。

よって、複数の選択肢からいずれか1つの型だけを選ぶデータ構造である代数的データ構造を使ってマッチングを行う。

代数的データ構造は、以下のように具体的なデータは作らず、(pattern) => return pattern.XXXという関数を返す。

const empty = () => {
  return (pattern) => {
    return pattern.empty();
  };
};

const cons = (value, list) => {
  return (pattern) => {
    return pattern.cons(value, list);
  };
};

パターンマッチを実行するmatch関数の引数のdataには代数的データ構造、patternにはオブジェクト型のインスタンスが入る。
このインスタンスによって条件分岐を実行する。

const match = (data, pattern) => {
  return data(pattern);
};

代数的データ構造のリストに対するisEmptyをmatch関数を利用して実装する。
isEmptyは、引数に渡されたリストが空のリストかどうかを判定する。

const isEmpty = (alist) => {
  return match(alist, {
    empty: () => {
      return true;
    },
    cons: (head, tail) => {
      return false;
    },
  });
};

実際に使ってみると以下のようになる。

isEmpty(empty()); // true
isEmpty(cons(1, empty())) // false

1つ目のisEmpty(empty())から詳しく読む。

isEmptyの引数およびmatchの第一引数であるdataとなるempty()は以下の関数を返す。

(pattern) => {
   return pattern.empty();
};

また、patternは以下のオブジェクトである。

{
    empty: () => {
      return true;
    },
    cons: (head, tail) => {
      return false;
    },
}

よって、matchではpatternのemptyが実行され、trueが返る。

同じようにisEmpty(cons(1, empty()))を読んでいく。

consの定義をもう一度みてみると、以下である。

const cons = (value, list) => {
  return (pattern) => {
    return pattern.cons(value, list);
  };
};

よって、isEmptyの引数およびmatchの第一引数であるdataとなるcons(1, empty())は以下の関数を返す。

(pattern) => {
    return pattern.cons(1, (pattern) => {
                                             return pattern.empty();
                                            }
                                      );
};

よって、patternのconsが実行され、falseが返る。

次に、リストの先頭要素を調べるheadの定義を読む。

const head = (alist) => {
  return match(alist, {
    empty: () => {
      return null;
    },
    cons: (head, tail) => {
      return head;
    },
  });
};

実際に使ってみると以下のようになる。

head(cons(1, empty())) // 1

これは、引数は同じだが、patternのconsは以下のように第一引数のheadを返す。

{
    empty: () => {
      return null;
    },
    cons: (head, tail) => {
      return head;
    }
}

よって、1が返される。

これで代数的データ構造とパターンマッチは理解できた。
せっかくなのでTypeScriptを使用して型をつけていく。

まずは、完成した型の全体像が以下である。

type IsEmptyPattern = {
  empty: () => boolean;
  cons: (head: number, tail: EmptyReturn | ConsReturn) => boolean;
};

type HeadPattern = {
  empty: () => null;
  cons: (head: number, tail: EmptyReturn | ConsReturn) => number;
};

type isEmptyReturn = ReturnType<typeof isEmpty>;
type headReturn = ReturnType<typeof head>;

type EmptyReturn = ReturnType<typeof empty>;
type ConsReturn = ReturnType<typeof cons>;

const empty = (): ((
  pattern: IsEmptyPattern | HeadPattern
) => boolean | null) => {
  return (pattern: IsEmptyPattern | HeadPattern) => {
    return pattern.empty();
  };
};

const cons = (
  value: number,
  list:
    | EmptyReturn
    | ((pattern: IsEmptyPattern | HeadPattern) => boolean | number)
): ((pattern: IsEmptyPattern | HeadPattern) => boolean | number) => {
  return (pattern: IsEmptyPattern | HeadPattern) => {
    return pattern.cons(value, list);
  };
};

const match = (
  data: EmptyReturn | ConsReturn,
  pattern: IsEmptyPattern | HeadPattern
): boolean | null | number => {
  return data(pattern);
};

const isEmpty = (alist: EmptyReturn | ConsReturn): boolean => {
  return <boolean>match(alist, {
    empty: () => {
      return true;
    },
    cons: (head: number, tail: EmptyReturn | ConsReturn) => {
      return false;
    },
  });
};

const head = (alist: EmptyReturn | ConsReturn): null | number => {
  return <null | number>match(alist, {
    empty: () => {
      return null;
    },
    cons: (head, tail) => {
      return head;
    },
  });
};

isEmpty(empty()); // ture
isEmpty(cons(1, empty())); // false
head(cons(1, empty())); // 1

isEmpty、head関数で使われているpatternの型を定義する。
また、empty、cons、isEmpty、head関数の戻り値をReturnTypeでとっている。
isEmpty、head関数の戻り値にType assertionsをつけているのは、以下のようなエラーが出たので誤魔化した。
Type 'number | boolean | null' is not assignable to type 'boolean'. Type 'null' is not assignable to type 'boolean'.
consの第二引数listの型は、EmptyReturn | ConsReturnにしたらType alias 'ConsReturn' circularly references itself.のエラーが出たので自己参照しないようにした。
Type alias circularly references itself · Issue #14174 · microsoft/TypeScript · GitHub
この辺りで議論されているけど力尽きたのでとりあえずこのままにしておく。

この先もサンクを無限を表現するとか難しそうな項目があるのでじっくり進めていきたい。

経験は何よりも饒舌

10年後に真価を発揮するかもしれないブログ

「関数型プログラミングの基礎」代数的データ構造とパターンマッチを理解する