list - 如何在 OCaml 中取两个列表的乘积？

Question

我有两个清单：

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

我想要一个输出列表 c 例如：

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

由于列表是不可变的，如何在 ocaml 中执行此操作？我是新手。

Answer 1

您将返回一个新列表。如果您真的对列表的笛卡尔积感兴趣，那么这应该足够了：

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 2

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

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

进入

(a,b)::y

Answer 3

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

• 首先考虑一个函数 appendeach ，它接受一个值和一个列表，并返回在列表中每个项目前面添加该值的结果

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

• 然后考虑一个带有两个列表的函数产品，并为第一个列表和整个第二个列表中的每个项目调用 appendeach

  let rec product lst1 lst2 = match lst1 with [] -> [] | 
                                           hd::tl -> (appendeach hd lst2)@(product tl lst2);;
  

Answer 4

这是基于 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"; "%"]]

如果您随后需要一个扁平列表，您可以List.concat按照其他答案将其包装起来：

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

Answer 5

一个非常必要的（类 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;;