Cartesian product two lists [duplicate]

Question

This question already has answers here:

Closed 9 years ago.

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) 

Answer 1

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))