7

Possible Duplicate:
F# - cross product of two lists
Projecting a list of lists efficiently in F#

I have a function that takes two integer lists and returns a single list with all the cartesian products. I think i have the correct idea but not the right implementation. Can I get some pointers?

let rec cartesian = function
 | ([],[]) -> []
 | (xs,[]) -> []
 | ([],ys) -> []
 | (x::xs,ys) ->   List.map(fun y -> (x,y)::[]) cartesian (xs,ys)
Community
  • 1
  • 1
user1072706
  • 573
  • 2
  • 8
  • 20

1 Answers1

13

This is a quick fix:

let rec cartesian = function
 | ([],[]) -> []
 | (xs,[]) -> []
 | ([],ys) -> []
 | (x::xs, ys) -> (List.map(fun y -> x,y) ys) @ (cartesian (xs,ys))

The idea is that with each element x, you generate a list [(x, y1); (x, y2); ...; (x, yn)] and concatenate those lists altogether.

In your function, the first pattern matching case is redundant. And the arguments are more convenient to be in the curried form. The function could look like this:

let rec cartesian xs ys = 
  match xs, ys with
  | _, [] -> []
  | [], _ -> []
  | x::xs', _ -> (List.map (fun y -> x, y) ys) @ (cartesian xs' ys)

Once you understand the idea, you can see that the high-order function List.collect perfectly matches the task:

let cartesian xs ys = 
    xs |> List.collect (fun x -> ys |> List.map (fun y -> x, y))
pad
  • 41,040
  • 7
  • 92
  • 166
  • could you please explain this part List.map(fun y -> x,y) ys) ... also I am puzzled as of how the list.map function knows which list to use.. in this case ys and not xs – user1072706 Feb 09 '12 at 15:51
  • 1
    You're decomposing `xs`, so for each element `x` you need to traverse through the whole `ys` to create a list of pairs `(x, yi)`. In the end, the result is a list of all pairs `(xi, yi)` where `xi` from the first list and `yi` from the second one. – pad Feb 09 '12 at 16:00