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 = 
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 -> 
      (fun n->f0 n (carts (Seq.skip 1 nss))) 
      (Seq.head nss) 

No comments: