関数型プログラミングとはなんぞや？ということを最近調べています。 その過程で気づいた、高階関数とカリー化された関数の関係についての備忘録です。

関数型プログラミング入門の中盤頃に有る、 「宣言を除去する」を参考に、以下のような関数を考えます。

仕様

1. 関数zeroは、int型のリストを受け取り、先頭要素が0なら、リストの残りを返す。違うならNoneを返す。
2. 関数oneは、int型のリストを受け取り、先頭要素が1なら、リストの残りを返す。違うならNoneを返す。

素直な実装

OCamlでとりあえずシンプルに書くと、以下のような感じになると思います。

let zero = function
  | [] -> None
  | hd :: tl -> if hd = 0 then Some tl else None

let one = function
  | [] -> None
  | hd :: tl -> if hd = 1 then Some tl else None

assert( (zero [0;1;2]) = (Some [1;2]) );;
assert( (zero [1;1;2]) = None );;
assert( (one [0;1;2;3]) = None );;
assert( (one [1;2;3]) = (Some [2;3]) );;

高階関数で重複を省く

上記のコードでも動きますが、関数zeroとoneはifで比較している値が違うだけです。 なので、比較対象の値を受け取り、その値を使って判断をする 関数を返す関数 を作ってコードの共通化を図ります。 いわゆる高階関数ですね。

let create_rule value =
  (fun v ->
     match v with
     | [] -> None
     | hd :: tl -> if hd = value then Some tl else None
  )
let zero = create_rule 0
let one = create_rule 1

assert (((create_rule 100) [100; 101; 102] ) = (Some [101; 102]));;
assert (((create_rule 100) [0; 101; 102] ) = None);;
assert( (zero [0;1;2]) = (Some [1;2]) );;
assert( (zero [1;1;2]) = None );;
assert( (one [0;1;2;3]) = None );;
assert( (one [1;2;3]) = (Some [2;3]) );;

問題なく動いているし、コードも明らかにスッキリしました。 なお、上記は無名関数を返すようにしていますが、以下のように一旦変数に入れてもOKです。

let create_rule value =
  let f v =
    match v with
    | [] -> None
    | hd :: tl -> if hd = value then Some tl else None
  in
  f
let zero = create_rule 0
let one = create_rule 1

高階関数の型をよく見ると？

さて、実際に定義したcreate_ruleという高階関数ですが、OCamlによって推論された型を見てみると以下のようになっています。

'a -> 'a list -> 'a list option

コレはつまり、「引数として'a型の値と'a型の値のリストを受け取り、'a型の値の入ったリストをOptionに包んで返す」という関数ということです。

ココには、「高階関数ですよ」という情報は全く現れていません。ただのOCamlの関数です。 試しに以下のような関数を定義しても全く同じ型情報になります。

utop # let f a b = Some (a :: b);;
val f : 'a -> 'a list -> 'a list option = <fun>

OCamlの関数は常にカリー化されるので、上記のように態々「関数を返す関数」を用意して、返された関数を利用する、というような書き方をする必要はありません。

なので、実際には以下のように書き直すことができます。

カリー化された関数

let create_rule value value_list =
  match value_list with
  | [] -> None
  | hd :: tl -> if hd = value then Some tl else None

let zero = create_rule 0
let one = create_rule 1

実行結果も全く同じです。

assert (((create_rule 100) [100; 101; 102] ) = (Some [101; 102]));;
assert (((create_rule 100) [0; 101; 102] ) = None);;
assert( (zero [0;1;2]) = (Some [1;2]) );;
assert( (zero [1;1;2]) = None );;
assert( (one [0;1;2;3]) = None );;
assert( (one [1;2;3]) = (Some [2;3]) );;

ちなみに、OCamlの場合はfunctionキーワードを使うことで、関数の最後の引数を自動的にmatch式で扱えるようになるのでコードがスッキリします。 以下のように書いても全く同じになります。

let create_rule value = function
  | [] -> None
  | hd :: tl -> if hd = value then Some tl else None

let zero = create_rule 0
let one = create_rule 1

まとめ

OCamlとElmという関数型プログラミング言語を勉強していますが、いまいち「関数型プログラミングって結局何？」という部分がまだはっきりと理解できていません。 その学習の過程で、OCamlで関数を返す関数は、普通にカリー化された関数なんだよ、という事実に気づけたのでそのメモです。 おそらくHaskelやElmでも全く同じ感じなのでは無いかな？と想像しています。 もし何か勘違いしているぞ！という指摘などあればTwitterにて優しく教えて頂ければ嬉しいです。