OCaml 列表的笛卡尔（外）积

Question

我想遍历列表列表中元素的所有组合，这些列表具有相同的长度但不一定是相同的类型。这就像两个列表的笛卡尔积（在 OCaml 中很容易做到），但对于任意数量的列表。

首先，我尝试编写一个通用的笛卡尔（外）乘积函数，该函数采用列表列表和 returns 元组列表，但这行不通，因为列表的输入列表不会有相同类型的元素。

现在我归结为

类型的函数

'a list * 'b list * 'c list -> ('a * 'b * 'c) list

不幸的是，这将输入的数量固定为三个（例如）。这是

let outer3 (l1, l2, l3) =
   let open List in
   l1 |> map (fun e1 -> 
       l2 |> map (fun e2 ->
           l3 |> map (fun e3 ->
               (e1,e2,e3))))
   |> concat |> concat

这可行，但很麻烦，因为必须为每个输入数量重做。有更好的方法吗？

背景：我想将生成的平面列表提供给 Parmap.pariter。

Answer 1

为了解决任意 ntuple 的任务，我们需要使用存在类型。我们可以使用 GADT，但默认情况下它们是关闭的。当然我们可以使用开放变体，但我更喜欢使用第一个 class 模块的语法更繁琐但更便携的解决方案（它之所以有效，是因为 GADT 可以通过第一个 class 模块成为 expressed） .但是足够的理论，首先我们需要一个函数来为我们生成 n_cartesian_product，类型为 'a list list -> 'a list list

let rec n_cartesian_product = function
  | [] -> [[]]
  | x :: xs ->
    let rest = n_cartesian_product xs in
    List.concat (List.map (fun i -> List.map (fun rs -> i :: rs) rest) x)

现在我们需要将不同的类型归为一个类型'a，而存在类型来了，让我们定义一个签名：

module type T = sig
  type t
  val x : t
end

现在让我们尝试为这个存在写一个提升器：

let int x  = (module struct type t = int let x = x end : T)

它有类型：

int -> (module T)

让我们用更多案例扩展示例：

let string x = (module struct type t = string let x = x end : T)
let char x = (module struct type t = char let x = x end : T)

let xxs = [
  List.map int [1;2;3;4];
  List.map string ["1"; "2"; "3"; "4"];
  List.map char ['1'; '2'; '3'; '4']
]

# n_cartesian_product xxs;;
- : (module T) list list =
[[<module>; <module>; <module>]; [<module>; <module>; <module>];
 [<module>; <module>; <module>]; [<module>; <module>; <module>];
 ...

如果您的类型要求允许（例如，如果您不需要公开类型 t），您可以使用其他抽象，如对象或函数，而不是第一个 class 模块。当然，我们的existential很简洁，也许你会需要扩展签名。

Answer 2

我使用了@ivg 的答案，但使用的是带有 GADT 的版本。我在这里复制它以供参考。在输入列表中只能出现类型 float 和 int 的简单情况下，首先设置

type wrapped = Int : int -> wrapped | Float : float -> wrapped

这是一个没有类型参数的 GADT。那么

let wrap_f f = Float f
let wrap_i i = Int f

将类型包装成求和类型。在 wrapped 值列表中，我们可以从 @ivg 的回答中调用 n_cartesian_product。结果是一个列表 combinations: wrapped list list，它是扁平的（对于当前目的）。

现在要使用 Parmap，我有例如辅助函数 work : float * int * float * float -> float。为了从包装器中获取参数，我进行了模式匹配：

combinations |> List.map (function 
 | [Float f1; Int i; Float f2; Float f3] -> (f1, i, f2, f3)
 | _ -> raise Invalid_argument "wrong parameter number or types")

构建平面元组列表。这最终可以通过 worker 函数 work 馈送到 Parmap.pariter。

此设置几乎与使用常规求和类型 type wrapsum = F of float | I of int 而不是 wrapped 相同。模式匹配是一样的；唯一的区别似乎是输入错误，例如(F 1, I 1, F 2.0, F, 3.0) 只会在运行时检测到，而不是像这里那样在编译时检测到。

OCaml 列表的笛卡尔（外）积

Cartesian (outer) product of lists in OCaml

polymorphism

ocaml

tuples

list