F#でリスト要素のデカルト積を求める
二つのリスト
[0; 1]
[2; 3]
のデカルト積（Cartesian product）、つまり互いのリスト要素どうしのすべての組み合わせによる集合をリストで表すと
[ [0; 2]; [0; 3]; [1; 2]; [1; 3] ]
と表せます。また、三つのリスト
[0; 1]
[2; 3]
[4; 5]
ならば
[ [0; 2; 4]; [0; 2; 5]; [0; 3; 4]; [0; 3; 5]; [1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5] ]
と表せます。Haskellなどの文法と違って、F#はリスト要素を','（コンマ）ではなく';'（セミコロン）で区切ります。（F#でコンマはタプル（tuple）の要素を区切るときに使います。）
複数のリストのデカルト積を求めるコードをF#で書いてみます。参考にした資料は『Thinking Functionally with Haskell』chapter 5 - A simple Sudoku solver。資料中にある以下のHaskellのコードの動作をF#で真似してみます。
cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- yss]
where yss = cp xss
これをF#でできるだけ似た形のコードに書き直してみます。
// 再帰呼び出しがあるので'rec'を付ける let rec cartesianp (sources: list<list<'a>>): list<list<'a>> = match sources with | [] -> [[]] | xs::xss -> // Haskellと違ってcons演算子のコロンは二つ [ for x in xs do for ys in (cartesianp xss) do // 再帰呼び出し yield x::ys ]
Haskellの多相データ型の型変数に似た文法として、F#ではジェネリック型パラメータを「'a」のようにシングルクォートで始まる識別子を使って書くことができます。
再帰呼び出しとリスト内包表記（list comprehension）を用いています。F#にはHaskellのwhere節に相当する文法はないので、再帰呼び出し箇所はリスト内包表記部分の内側に直接埋め込んであります。
F#にもリスト内包表記の文法があるためHaskellのリスト内包表記に似たコードの書き方ができます。ただしHaskellと違って遅延評価は行われません。
Visual Studio の F# Interactive の環境でこの関数を実行してみます。
実行例
> cartesianp [[0;1]; [2; 3]];;
val it : int list list = [[0; 2]; [0; 3]; [1; 2]; [1; 3]]
> cartesianp [[0;1]; [2; 3]; [4; 5]];;
val it : int list list =
[[0; 2; 4]; [0; 2; 5]; [0; 3; 4]; [0; 3; 5]; [1; 2; 4]; [1; 2; 5]; [1; 3; 4];
[1; 3; 5]]
さらにプログラマ向け質問サイト Stack Overflow にもデカルト積に関連する質問が載っていたので参考にしました。こちらのコードもHaskellで書かれています。
cartesianProduct :: [[a]] -> [[a]]
cartesianProduct sequences = foldr aggregator [[]] sequences
where aggregator sequence accumulator =
[ item:accseq |item <- sequence, accseq <- accumulator ]引用元：haskell - Calculate n-ary Cartesian Product - Stack Overflow
リストの右畳み込み（foldr）を使ったコードが載っているのでこれをF#の標準ライブラリでも用意されている右畳み込み関数foldBackを利用して書き直してみます。
let cartesianProduct (sequences: list<list<'a>>) : list<list<'a>> = let aggregator (sequence: list<'a>) (accumulator: list<list<'a>>) : list<list<'a>> = [ for item in sequence do for accseq in accumulator do yield item::accseq ] List.foldBack aggregator sequences [[]] // 引数の順序がHaskellとは異なるので注意
F#にはfoldrという関数はないので同様の機能を持つList.foldBackで代用しています。ただし、Haskellのfoldrとは引数の与え方が異なるので注意が必要です。
また、where節に相当する文法はないので、where節に書かれた内容をList.foldBackを呼び出す行よりも前の位置に書いています。
実行例
> cartesianProduct [[0; 1]; [2; 3]];; val it : int list list = [[0; 2]; [0; 3]; [1; 2]; [1; 3]]
> cartesianProduct [[0; 1]; [2; 3]; [4; 5]];; val it : int list list = [[0; 2; 4]; [0; 2; 5]; [0; 3; 4]; [0; 3; 5]; [1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]]
