OCaml版パスカルの三角形

さて、LinuxではF#は使えない(※1)んで、OCamlで書いてみる。

let f lst =
　let rec loop x0 x1 xs acc = match xs with
　　　[] -> (x0 + x1)::acc
　　| first::rest -> loop x1 first rest ((x0 + x1)::acc) in
　loop (List.hd lst) (List.nth lst 1) (List.tl (List.tl lst)) []

let last lst =
　List.hd (List.rev lst)

let pascal n =
　let rec loop n acc = match n with
　　　0 -> [List.hd acc]
　　| 1 -> acc
　　| _ -> loop (n - 1) (acc @ [(1::((f (last acc)) @ [1]))]) in
　loop n [[1]; [1; 1]]

多分F#で正攻法で書けば、似たようなコードになるだろう。

OCamlはリストの最後を取り出すlastが無い。いや、Schemeにも仕様上ねぇけどな(笑)。ただ、Racketはデカいんで、色々ショートカットが可能だ、と言う事だ。

ただ、ライブラリの充実度はOCamlとF#だと差があるかもしんない。OCamlにも外部ライブラリはあるが、そこはMicrosoft、抜け目はないと思う。

なお、OCamlの@はappendの演算子版だ。

参考: => ソースコードその1

もう1つ、「関数型言語っぽい」プログラムとしては、高階関数mapとreduce(fold)を使う手がある。

次のように書いてみよう。

let butlast lst =
　(List.rev (List.tl (List.rev lst)))

let last lst =
　List.hd (List.rev lst)

let pascal n =
　List.fold_left (fun x y -> match y with
　　　　0 -> x
　　　| 1 -> x @ [[y; y]]
　　　| _ -> let lst = last x in
　　　　x @ [1::((List.map2 (+) (butlast lst) (List.tl lst)) @ [1])])
　[[1]] (0::(List.init n (fun x -> x + 1)))

まず、リストの最後の要素を削除する関数butlastを書く。Scheme(のSRFI-1)やRacketだったらtakeを使う辺りだが、ここではANSI Common Lispのbutlastに倣った。

これはmapに於いての演算で、引数のリストの長さの帳尻を合わせる為、に使う(※2)。

例えば、今欲しいパスカルの段を計算する為に前の段のリストが次のようなものだったとする。

[1; 3; 3; 1]

次の段の両辺(つまり1と1だ)を省いた部分の計算は当然、1 + 3、3 + 3、3 + 1でないとならない。

この計算法だが、要するに

[1; 3; 3] (* リストの末尾を削除したリスト *)
[3; 3; 1] (* リストの先頭を削除したリスト *)

それぞれの要素を「縦に」足せば結果が出る。

このために、高階関数mapを用いて

List.map2 (+) [1; 3; 3] [3; 3; 1]

と計算すればいい。

そこを一般化すると、

List.map2 (+) (butlast lst) (List.tl lst))

となる次第だ。

なお、List.tlはLispのcdrに相当する。

あとは、foldを使って条件によって初期値 [[1]] に計算結果をケツからappendしていけばパスカルの三角形、データ上は「リストのリスト」を生成していける。

あと、もう1つOCamlで厄介なのはPythonやRacketでのrange関数が無い辺りだ。

range関数代わりに

(0::(List.init n (fun x -> x + 1)))

と言う若干トリッキーな記述をせざるを得なかった。この部分はカウンターで、foldが取るラムダ式の条件を変える役目を担ってる。0段目と1段めだけはちとプログラミング上、スムースに計算が運ばない為、こういうrange紛いのトリックを仕込んだ。この辺はF#でも似たようなトリックを使わないとならないんじゃないか。

いずれにせよ、最初の(パターンマッチング込みの)再帰版をまずは押さえて、余裕があったら高階関数版の理解に挑戦する、って程度でいいと思う。

参考: => ソースコードその2

※1: 正確には、.NETの互換、Monoを使えば使えるらしい(時代も変わったモンだ)。

が、僕が愛用してるScheme処理系、Chicken Schemeとコンフリクトするんで(Xubuntuの親玉、Debianの問題らしい)、生憎僕のPCでは使えない。

※2: Schemeの仕様書に拠ると、mapは可変長引数だが、長さの違うリストが混在する場合、短いリストに合わせて演算が終了する。

一方、Racketのmapは引数として取ったリストは全部長さが一致してなければならない、と言う縛りが存在して、OCamlのmapも実はRacketと全く同じになっている。

また、OCamlのmapは可変長引数を取らず、引数リストが1つのmapと引数リストが2つのmap2が提供されてるのみ、だ。

なお、F#の場合は、加えてリスト引数を3つ取れるmap3と言う高階関数も提供されてる模様だ。