ocaml - 任意深度的步行 OCaml 元组

Question

我试图更好地理解 OCaml 类型推断。我创建了这个例子:

let rec f t = match t with
    | (l,r) -> (f l)+(f r)
    | _ -> 1

我想将它应用于任何带有嵌套对的二进制元组(对)，以获得叶子的总数。示例:f ((1,2),3)

函数 f 拒绝编译，因为 (f l) 处的类型矛盾:“此表达式具有类型 'a，但预期的表达式类型为 'a * 'b”。

问题:'a 是任何类型，不能也是一对，否则由 _ 情况处理？是否有任何方法可以遍历任意深度的元组而不将它们转换为其他数据结构，例如变体？

PS:在 C++ 中，我会通过创建两个模板函数“f”来解决此类问题，一个用于处理元组，另一个用于处理其他类型。

Answer 1

有一种方法可以做到这一点，但由于其复杂性，我不会向新用户推荐它。你应该先习惯编写常规的 OCaml。

也就是说，您可以通过将必要的结构捕获为 GADT 以通用方式遍历任意类型。对于这个简单的问题，这很容易:

type 'a ty =
  | Pair : 'a ty * 'b ty -> ('a * 'b) ty
  | Other : 'a ty

let rec count_leaves : type a . a -> a ty -> int =
  fun a ty ->
    match ty with
    | Pair (ta, tb) -> count_leaves (fst a) ta + count_leaves (snd a) tb
    | Other -> 1

请注意此处 a ty 上的模式匹配与您的(类型不佳的)示例函数中的值的模式匹配是如何对应的。

更有用的函数可以用更完整的类型表示来编写，尽管一旦必须支持任意元组、记录、总和类型等，机器就会变得沉重和复杂。