走任意深度的OCaml元组

Question

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

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

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

函数f拒绝编译,因为(fl)类型中的矛盾:"此表达式具有类型'a但是表达式需要类型'a*'b".

问题:'a是任何类型,也不能是一对,或者由_ case处理？是否有任何方法来处理任意深度的元组而不将它们转换为其他数据结构,例如变体？

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这里的模式匹配如何对应于(类型不佳的)示例函数中的值的模式匹配.

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