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

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 2

Just came across a rather elegant solution to this using computation expressions:

type Product () =
  member this.Bind (l,f) = List.collect f l    
  member this.Return n = [n]

let enumeratedPizzas = 
  Product() {
    let! x = ["New York";"Chicago"]
    let! y = ["Pepperoni";"Sausage"]
    let! z = ["Cheese";"Double Cheese"]
    return x,y,z
  }

By Techneilogy, copied from fssnip.net, follow the link to see commented code.

Answer 3

I recently needed something similar - I had to zip a list of sequences to a sequence 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)  
   }

Answer 4

As of F# 4.0, you can use List.allPairs to give the Cartesian product of two lists. If you have n lists, see How do I compute the cartesian product of n sequences in F#?

Answer 5

I was using Benjol answer for a while until I found that you can pretty much do the same thing with Linq. Benjol's solution is probably still the most elegant but if anyone wants a solution that you can use with C# also then here you go:

query {
  for i in [1, 2] do
  for j in [3, 4] do
  select (i, j)
}

Which is almost exactly the same as Tomas Petricek's solution except the solution doesn't need to be nested for loops so it is slightly simpler.

Answer 6

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 { ... }.