F# - 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

Hi, 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

Your crossproduct function looks good (you've probably noticed the missing "in" keywords). I like this version of crossproduct3 better, but that's just me :

let crossproduct3 l1 l2 l3 = 
List.map_concat 
(fun z ->
 (List.map_concat (fun y -> List.map (fun x -> (x, y, z)) l3) l2)) l1;;

Your function has an equivalent algorithmic complexity.

Finally, when using crossproduct on an explicitly empty list, you may hit on the value restriction (roughly, a restriction that makes sure the compiler only infers polymorphic types for a syntactic value), that is particularly strict in F#. The solution is to annotate calls that use an empty list, in the following way (if you want the second list to be composed of integers):

(crossproduct [3; 4] [] : (int * int) list)

Answer 3

I recently needed something similar - I had to zip a list of sequences to a seqenz of lists - so [(a1,a2,a3,...);(b1,b2,b3,...);(c1,c2,c3,...)] -> ([a1;b1;c1], [a2;b2;c3], ...)

The following code will do this:

let rec listZip (sl : 'a seq list) =
seq {
match sl with
| [] -> yield []
| hd::tl ->
for h in hd do
for t in listZip tl do
yield (h::t)
}