OCamlのお勉強 その6 〜多相と型推論、コンビネータ〜

「プログラミング in OCaml ~関数型プログラミングの基礎からGUI構築まで~」を読んでの勉強記録です。

型推論によって型が確定されない引数を持つ関数は多相的関数となる。

# let add x y = x + y;;
val add : int -> int -> int = <fun>
# let k x y = x;;
val k : 'a -> 'b -> 'a = <fun>

関数addはint型の値x、yを受け取ってint型の値を返す関数となっているのに対し、関数kは何らかの型'a、'bの値x、yを受け取って'a型の値を返す関数となっています。addについてはx + yという式からx、yはint型だと推論できますが、kについてはx、yの具体的な型は決めようがありません。こういった関数を多相的関数というそうです。C#で近い機能というとジェネリクスですね。

この本では、ケーススタディとしてコンビネータに触れています（アカデミックですね！）。最近Yコンビネータで話題のあれです。先ほどの関数kは、基本となる2つのコンビネータのうちの1つで、Kコンビネータと呼びます。もうひとつはSコンビネータです。

# let s x y z = x z (y z);;
val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>

Kは定数関数を返す関数で、Sは置換演算子（なんでこう呼ぶのかはわかりません）です。Kについては、「定数関数を返す」ということをそのまま表現すると

# (* xを受け取り、どんな引数だろうと常にxを返す関数を返す *)
  let k x = fun y -> x;;
val k : 'a -> 'b -> 'a = <fun>

とも書けますね。SとKの組み合わせで様々な関数を構築できます。S、Kの組み合わせの単純な例としてIコンビネータがあります。

# s k k 19;;
- : int = 19
# s k k "hello";;
- : string = "hello"

Iコンビネータは与えられた引数をそのまま返す恒等関数です。なぜこのような動作するのでしょうか。擬似コードで関数適用の流れを追ってみます。

s x y = fun z -> x z (y z)        (* sの書き直し *)
s k k = fun z -> k z (k z)        (* x、yをkで置き換え *)
      = fun z -> k z (fun a -> z) 
      = fun z -> z                (* k x y = xより *)

確かにs k kは恒等関数となっています。コンビネータに関する練習問題も解いてみました。

恒等関数を、s k kで表現したように、関数fun x y -> yをコンビネータsとkを関数適用のみで（funやletによる関数定義を使わずに）組み合わせた形で表現しなさい。

4.4 練習問題，p83

# k (s k k);;
- : '_a -> '_b -> '_b = <fun>
# k (s k k) 0 1;;
- : int = 1
# k (s k k) 0 "later";;
- : string = "later"

合っていそうです。先ほどのように関数適用の流れを追ってみます。

k (s k k) = k (fun y -> y)
          = fun x -> (fun y -> y)
          = fun x y -> y

確かにfun x y -> yとなっています。

今回はここまで。次回はリストについてです。