如何在OCAML中使用两个列表的产品？ 我有两个列表： 令A = [“ A”;“ B”]; 令B = [“ C”;“ D”]; 我想要一个输出列表C，例如： c = [“ a”;“ c”;“ a”;“ d”;“ b”;“ c”;“ b”;“ d”]; 如何在OCAML中做到这一点，因为列表是不可变的？我是新来的。

Question

c = ["a";"c";"a";"d";"b";"c";"b";"d"];

如何在OCAML中进行，因为列表是不变的？我是新来的。 您将返回新列表。如果您真的对列表的cartesian产品感兴趣，那么这应该足够：

let cartesian l l' = 
  List.concat (List.map (fun e -> List.map (fun e' -> (e,e')) l') l)

# cartesian ["a";"b"] ["c";"d"];;
- : (string * string) list = [("a", "c"); ("a", "d"); ("b", "c"); ("b", "d")]

如果您需要那种奇怪的平坦结构，则可以使用其他列表串联。

let flat_cartesian l l' = 
  List.concat (List.concat (
    List.map (fun e -> List.map (fun e' -> [e;e']) l') l))

Answer 1

如果您不想使用串联，因为这不是尾部递归操作，则可以使用以下（应该更有效）：

let product l1 l2 =
  List.rev (
   List.fold_left
    (fun x a ->
      List.fold_left
       (fun y b ->
         b::a::y
       )
       x
       l2
   )
   []
   l1
 )
;;

对于笛卡尔产品，只需更改

b::a::y into

Answer 2

(a,b)::y

基于Python的

itertools.product

.

。

清单都必须是相同的类型，因为我们返回的产品本身将是（一定是同质）列表。

let product pools =
  let result = ref [[]] in
  List.iter (fun pool ->
      result := List.concat_map (fun y ->
          List.map (fun x ->
              List.append x [y]
            ) !result
        ) pool
    ) pools;
  !result

product [["a";"b"]; ["1";"2"]; ["$";"%"]];;
- : string list list =
[["a"; "1"; "$"]; ["b"; "1"; "$"]; ["a"; "2"; "$"]; ["b"; "2"; "$"];
 ["a"; "1"; "%"]; ["b"; "1"; "%"]; ["a"; "2"; "%"]; ["b"; "2"; "%"]]

Answer 3

List.concat

中：

List.concat (product [["a";"b"]; ["1";"2"]]);;
- : string list = ["a"; "1"; "b"; "1"; "a"; "2"; "b"; "2"]

我会把问题分解为两个子问题：

首先考虑一个带有值和列表的函数附录，并返回列表中每个项目的值添加该值的结果。

let rec appendeach x lst = 
  match lst with 
    [] -> [] 
  | hd::tl -> x::hd::(appendeach x tl);;

然后考虑一个带有两个列表的功能产品，并为第一个列表中的每个项目和整个列表中的每个项目调用Appendeach

Answer 4

• 映射是解决此问题的一种非常自然的解决方案。但是，它不是尾部回收，对于足够大的数据样本，将发生堆栈溢出。现在，您可以使用折叠

  thmscarle的答案中所示。 或者，您可以制作映射尾部回复。

let map_tailrec f lst =
  let rec aux lst k =
    match lst with 
    | [] -> k []
    | x::xs -> aux xs (fun i -> k (f x :: i))
  in
  aux lst Fun.id

• 我们可以用来轻度修改Victor Nicollet的功能

  let cartesian l l' = 
    l 
    |> map_tailrec (fun e -> map_tailrec (fun e' -> (e,e')) l') 
    |> List.concat
  

当然，

List.concat

Answer 5

let concat_tailrec lsts =
  let rec aux lsts k = 
    match lsts with
    | [] -> k []
    | []::xs -> aux xs k
    | (x::x')::xs -> aux (x'::xs) (fun i -> k (x :: i))
  in
  aux lsts Fun.id

现在我们可以写：

let cartesian l l' = 
  l 
  |> map_tailrec (fun e -> map_tailrec (fun e' -> (e,e')) l') 
  |> concat_tailrec

做到这一点，

cartesian仍然非常熟悉，但是通过解决较小的组件的尾随递归问题，我们已经解决了整体问题。

非常急切（类似Java的或类似于C）的解决方案，因此我不确定它会有所帮助；在像OCAML这样的功能性语言中，通常是预期的递归而不是循环。但是它有效：

let cartesianProduct list1 list2 =
    let product = ref [] in
    for i = 0 to List.length list1 - 1 do
        for j = 0 to List.length list2 - 1 do
            product:= !product @ [List.nth list1 i] @ [List.nth list2 j]
        done;
    done;
    !product;;