Calculating the Cartesian product of a list of numbers with F#

Question

I am new to f#

I am try to calculate the Cartesian products of a list of numbers. I "borrowed" this.

let xs = [1..99]
let ys = [1..99]
seq {for x in xs do for y in ys do yield x * y}

Is there a better or more elegant way?

Gary

Answer 1

Another possibiltiy to tackle the problem based on functionality provided by the List module would be:

let xs = [1..99]
let ys = [1..99]
let zs = xs |> List.collect (fun x -> ys |> List.map (fun y -> x*y))

which avoids the extra calls to .concat and should also do the job.

But I'd stick with your solution. It should be the most readable which is a real matchwinner. (Just try to read the codes out loud. Yours is perfectly understandable and Noldorins or mine are not.)

Answer 2

Disclaimer: I don't have a machine with the current F# installed, so I can't test my code. Basically, though, if you steal sequence from Haskell, you can write your program as

let cartesian = sequence >> List.map product

and run it as

cartesian [[1..99]; [1..99]]

Here's how to write sequence. It's a generalised version of the sequence expression you wrote. It just handles an unlimited number of lists: { for x in xs do for y in ys do for z in zs ... yield [x;y;z;...] }.

let rec sequence = function
  | [] -> Seq.singleton []
  | (l::ls) -> seq { for x in l do for xs in sequence ls do yield (x::xs) }
// also you'll need product to do the multiplication
let product = Seq.fold_left1 ( * )

Then you can write your program as

let cartesian xs ys = [xs; ys] |> sequence |> List.map product
// ... or one-argument, point-free style:
let cartesian' = sequence >> Seq.map product

You might have to change some Seqs to Lists.

However, the number of people who can guess the meaning of your non-general list comprehension is probably a lot more than will recognise the name sequence, so you're probably better off with the list comprehension. sequence comes in handy any time you want to run a whole list of computation expressions, though.