f# - 笛卡尔积两个 list

Question

这个问题已经在这里有了答案:




9年前关闭。

Possible Duplicate:
F# - cross product of two lists
Projecting a list of lists efficiently in 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)]并将这些列表完全连接在一起。

在您的函数中，第一个模式匹配的情况是多余的。而且，以 curry 形式表达观点更方便。该函数可能如下所示:

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