第7章: Hindley-Milner型システムとの対話

型の本質とは？

関数型プログラミングを学び始めたなら、すぐに型シグネチャの深みに没頭することになるでしょう。型はメタ言語として、異なる背景を持つ人々が簡潔かつ効果的に意思疎通することを可能にします。ここでは主に「Hindley-Milner」と呼ばれるシステムを使用して記述される型シグネチャについて、本章で詳細に検討していきます。

純粋関数を取り扱う際、型シグネチャが持つ表現力は自然言語のそれを遥かに凌駕します。これらのシグネチャは関数の核心的な秘密をささやきかけます。たった一行のコンパクトな記述から、振る舞いと意図を明らかにするのです。我々はここから「自由定理」を導出できます。型推論が可能なため明示的な型注釈は不要です。緻密に精度を調整することも、汎用的・抽象的に保つことも可能です。型はコンパイル時のチェックに有用なだけでなく、最高のドキュメンテーションとしての役割も果たします。こうした理由から、型シグネチャは関数型プログラミングにおいて極めて重要な役割を担っているのです──想像以上に。

JavaScript は動的型付け言語ですが、型概念を完全に排除しているわけではありません。文字列、数値、真偽値などの型は依然として存在します。単に言語レベルでの統合がなされていないだけで、実際にはプログラマの頭の中で型情報を管理しています。心配無用です。ドキュメンテーション目的でシグネチャを使用する場合は、コメントを使って対処可能です。

JavaScript には Flow や型付き方言である TypeScript などの型チェックツールが存在します。本書の目的は関数型コードを書くための技術を習得することですので、関数型言語で標準的に使用される型システムに準拠します。

秘儀伝承

数学書の古びた頁から、白論文の広大な海を渡り、土曜の朝の気軽なブログ記事の間を抜け、ソースコードの深奥に至るまで、私たちは Hindley-Milner 型シグネチャと出会います。この体系は非常にシンプルですが、完全に理解するには簡単な解説と実践が必要です。

// capitalize :: String -> String
const capitalize = s => toUpperCase(head(s)) + toLowerCase(tail(s));

capitalize('smurf'); // 'Smurf'

ここで、capitalize は String を受け取り String を返します。実装の詳細はさておき、注目すべきは型シグネチャです。

HM 体系では、関数は a -> b と記述され、a と b は任意の型を表す変数です。したがって capitalize のシグネチャは「String から String への関数」と解釈できます。つまり、入力として String を受け取り、出力として String を返すわけです。

他の関数シグネチャも見てみましょう:

// strLength :: String -> Number
const strLength = s => s.length;

// join :: String -> [String] -> String
const join = curry((what, xs) => xs.join(what));

// match :: Regex -> String -> [String]
const match = curry((reg, s) => s.match(reg));

// replace :: Regex -> String -> String -> String
const replace = curry((reg, sub, s) => s.replace(reg, sub));

strLength は前例と同様、String を受け取り Number を返します。

他は一見すると困惑するかもしれません。詳細を完全に理解していなくても、最後の型が戻り値と見なせます。例えば match の場合、「Regex と String を受け取り [String] を返す」と解釈できます。しかしここでは興味深い事象が起こっています。時間をとって説明しましょう。

match のシグネチャは次のようにグループ化可能です:

// match :: Regex -> (String -> [String])
const match = curry((reg, s) => s.match(reg));

括弧で最後の部分を囲むと新たな情報が明らかになります。これにより、「Regex を受け取り、String から [String] への関数を返す」と解釈できます。カリー化の特性から、実際に Regex を与えると String 引数を待つ関数が返されます。もちろんこの見方に拘る必要はありませんが、最後の型が戻り値になる理由を理解しておく価値はあります。

// match :: Regex -> (String -> [String])
// onHoliday :: String -> [String]
const onHoliday = match(/holiday/ig);

各引数はシグネチャの先頭から型を取り除いていきます。onHoliday は既に Regex を持つ match です。

// replace :: Regex -> (String -> (String -> String))
const replace = curry((reg, sub, s) => s.replace(reg, sub));

replace の完全な括弧表記を見れば分かるように、余分な表記は冗長になりがちなので通常省略します。全ての引数を一度に与えることも可能なため、「replace は Regex、String、別の String を受け取り String を返す」と考える方が容易です。

最後にいくつか補足事項:

// id :: a -> a
const id = x => x;

// map :: (a -> b) -> [a] -> [b]
const map = curry((f, xs) => xs.map(f));

id 関数は任意の型 a を受け取り、同じ型 a の値を返します。コードと同様に型でも変数を使用可能です。a や b のような変数名は慣例ですが、任意の名前に置換可能です。ただし同じ変数は同一の型を表します。重要な規則なので再確認しましょう: a -> b は任意の型から別の型への変換を表しますが、a -> a は同一型でなければなりません。例えば id は String -> String や Number -> Number にはなれますが、String -> Bool にはなり得ません。

map も同様に型変数を使用しますが、ここでは a と同じ型か異なる型かを示す b を導入します。このシグネチャを「map は型 a から型 b（同型でも可）への関数と a の配列を受け取り、b の配列を返す」と読むことができます。

願わくば、この型シグネチャの表現的な美しさに打ちのめされているでしょう。文字通り関数の動作を一語一語伝えています。a から b への関数と a の配列を与えると、b の配列を提供します。これが行うべき唯一の合理的な操作は、各 a に関数を適用することです。それ以外は明らかな虚偽となります。

型とその含意を推論する能力は、関数型の世界で大いに役立つ技術です。論文やブログ、ドキュメントが理解しやすくなるだけでなく、シグネチャ自体が機能を解説してくれます。流暢に読み解くには訓練が必要ですが、継続すれば、RTFM（マニュアルを読む）なしで大量の情報が入手可能になります。

理解度を試すために、さらにいくつか例を挙げます。

// head :: [a] -> a
const head = xs => xs[0];

// filter :: (a -> Bool) -> [a] -> [a]
const filter = curry((f, xs) => xs.filter(f));

// reduce :: ((b, a) -> b) -> b -> [a] -> b
const reduce = curry((f, x, xs) => xs.reduce(f, x));

reduce はおそらく最も表現力豊かな関数です。ただし難解ですので、理解に苦しんでも落胆しないでください。好奇心旺盛な方のために英語で説明しますが、シグネチャを自ら分析する方が教育的です。

では始めましょう...シグネチャを見ると、第1引数は b と a を受け取り b を生成する関数です。これらの a と b はどこから得られるのでしょうか？シグネチャの後の引数は b と a の配列であるため、b と各 a が入力されると推測できます。関数の結果が b であることから、最終的に渡された関数の最後の適用結果が出力値になると考えられます。reduce の動作を知れば、上記の考察が正確であると確認できます。

可能性の収束

型変数を導入すると、パラメトリック多相性と呼ばれる特異な特性が現れます。この特性は、関数が全ての型に対して一貫した動作をすることを規定します。検証してみましょう:

// head :: [a] -> a

head のシグネチャは [a] から a を返します。具体的な配列型以外の情報を持たないため、機能は配列操作に限定されます。a について何の情報も持たない場合、この関数は a に対しどのような操作が可能でしょうか？言い換えれば、a は特定の型ではないため、あらゆる型に対応可能でなければならず、その結果関数はすべての想定可能な型に対して一様に動作する必要があります。これがパラメトリック多相性の本質です。実装を推測するに、最初・最後・ランダムな要素を取得するのが合理的です。head という名称がヒントです。

別の例を示します:

// reverse :: [a] -> [a]

型シグネチャだけから、reverse が行いうる操作は何でしょうか？ここでも a に特化した操作は不可能です。a を別の型に変換することは b の導入が必要になります。ソート可能でしょうか？いいえ、あらゆる型をソートする情報が不足しています。再配置は可能でしょうが、予測可能な方法で一貫して行う必要があります。要素の削除や複製も考えられますが、多相型によって可能な振る舞いは著しく制約されています。

この可能性の収束により、Hoogle のような型シグネチャ検索エンジンで目的の関数を見つけられます。シグネチャに凝縮された情報は極めて強力です。

定理という名の自由

実装可能性の推論に加え、この種の推論は自由定理をもたらします。Wadler の関連論文から直接引用した定理例をいくつか紹介します。

// head :: [a] -> a
compose(f, head) === compose(head, map(f));

// filter :: (a -> Bool) -> [a] -> [a]
compose(map(f), filter(compose(p, f))) === compose(filter(p), map(f));

これらの定理を得るにはコード不要で、型から直接導出されます。最初の定理は、配列の head を取得して関数 f を適用する操作が、全要素に map(f) を適用した後に head を取得する操作と等価（かつ高速）であることを示します。

常識的と思われるかもしれませんが、コンピュータは常識を持ちません。こうした最適化を自動化する形式的な方法が必要です。数学は直観を形式化する手段を提供し、コンピュータ論理の厳密な世界で役立ちます。

filter の定理も同様です。フィルタリング条件をチェックするために f と p を合成し、map 経由で f を適用する（filter のシグネチャが a に変更を加えないことを保証）場合、f をマップした後に p 述語でフィルタリングする操作と常に等価です。

これらは二例に過ぎませんが、この推論はあらゆる多相型シグネチャに適用可能です。JavaScript では書き換え規則を宣言するツールが存在します。compose 関数自体を通じて実現することも可能です。可能性は無限に広がっています。

型制約

最後に留意すべきは、型をインタフェースに制約可能な点です。

// sort :: Ord a => [a] -> [a]

太矢印の左側には、a が Ord 型クラス を実装している必要があるという事実が記載されています。要するに、a は値の順序付けが可能でなければならない、ということです。Ord とは型付き言語における定義済みインタフェースで、要素の比較演算を提供します。これは a に関する情報を追加するだけでなく、sort 関数の動作領域を明確に制限します。こうしたインタフェース宣言を型制約と呼びます。

// assertEqual :: (Eq a, Show a) => a -> a -> Assertion

ここでは Eq と Show の二つの制約があります。これらは a の等値性チェックが可能であることと、値の文字列表現を生成できることを保証します。

後の章で制約例が増え、概念が具体化していきます。

まとめ

Hindley-Milner 型シグネチャは関数型プログラミングの世界に遍在します。読み書きは単純ですが、シグネチャのみでプログラムを理解する技術の習得には時間を要します。これより、各コード行に型シグネチャを追加して進めます。

第8章: データコンテナ