笛卡尔积两个列表

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