Декартово произведение двух списков

Question

Возможный дубликат:
F# - перекрестное произведение двух списков
Эффективное проектирование списка списков в F#

У меня есть функция, которая принимает два целочисленных списка и возвращает один список со всеми декартовыми произведениями. Я думаю, что у меня есть правильная идея, но не правильная реализация. Могу ли я получить некоторые указатели?

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

Answer 1

Это быстрое решение:

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

Идея в том, что с каждым элементом x, вы генерируете список [(x, y1); (x, y2); ...; (x, yn)] и объединить эти списки в целом.

В вашей функции первый случай сопоставления с образцом избыточен. И аргументы удобнее быть в карри. Функция может выглядеть так:

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

Как только вы поймете идею, вы увидите, что функция высшего порядка List.collect идеально соответствует задаче:

let cartesian xs ys = 
    xs |> List.collect (fun x -> ys |> List.map (fun y -> x, y))