Tuesday, July 27, 2010

Cartesian Product of Lists in F#

A problem came up on stackoverflow: how to compute the Cartesian product of several sequences in F#? The poster wanted a solution involving sequences, presumably to meet external requirements, so my solution below using lists wasn’t quite right. But I decided to post it here anyway, since it illustrates my current F# learning goal:

Leveraging as much of the built-in power of the F# language and libraries as possible when solving a problem.

So without further ado (other than to note that all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk) here is my Cartesian product of lists code. It’s fairly compact, but there may be even more succinct solutions.

// Cartesian product of a list of lists.
let rec cart nll =
let f0 n = function
| [] -> [[n]]
| nll -> List.map (fun nl->n::nl) nll
match nll with
| [] -> []
| h::t -> List.collect (fun n->f0 n (cart t)) h

// Test.

let s =
[
[0;1;2;];
[3;4;];
[5;6;7;];
]

cart s |> List.iter (printfn "%A")

And here's a transliteration into sequences (but there may be a better way):

// Cartesian product of a seq of seqs.
let rec carts (nss:seq<seq<int>>) =
let f0 n (x:seq<seq<int>>) =
match Seq.isEmpty x with
| true -> seq{yield seq{yield n}}
| _ -> Seq.map (fun nl->seq{yield n;yield! nl}) x
match Seq.isEmpty nss with
| true -> Seq.empty
| false ->
Seq.collect
(fun n->f0 n (carts (Seq.skip 1 nss)))