Cross product of two lists

Question

Messing around with 'extension functions' for the List module. (I spent quite a while developing 'mapfold' - which threads an accumulator like fold, but uses it as a parameter to create new values like map - then discovered that that is what List.scan_left does)

For generation of test data, I needed to do a cross product of two lists, This is what I came up with:

///Perform cross product of two lists, return tuple
let crossproduct l1 l2 =
    let product lst v2 = List.map (fun v1 -> (v1, v2)) lst
    List.map_concat (product l1) l2

Is this any good, or is there already some better way to do this?

Same question for this one:

///Perform cross product of three lists, return tuple
let crossproduct3 l1 l2 l3 =
    let tuplelist = crossproduct l1 l2 //not sure this is the best way...
    let product3 lst2 v3 = List.map (fun (v1, v2) -> (v1, v2, v3)) lst2
    List.map_concat (product3 tuplelist) l3

Answer 1

another option is to use F# "sequence expressions" and write something like this:

let crossproduct l1 l2 =
  seq { for el1 in l1 do
          for el2 in l2 do
            yield el1, el2 };;

(actually, it is almost the same thing as what you wrote, because 'for .. in .. do' in sequence expression can be viewed as map_concat). This works with (lazy) sequences, but if you want to work with lists, you'd just wrap the code inside [ ... ] rather than inside seq { ... }.

Answer 2

As of F# 4.0, you can use List.allPairs to give the Cartesian product of two lists.

If you have more than two lists, see How do I compute the cartesian product of n sequences in F#?