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.

Answer 3

There is indeed a slightly more elegant way (at least in the functional sense) to calculate the Cartesian products, which uses the functions that exist within the List class. (There's no need to involve sequences or loops here, at least not directly.)

Try this:

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

Slightly longer admittedly, though more functional in style, it would seem.