首页 文章

走任意深度的OCaml元组

提问于
浏览 次
3

我试图更好地理解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是任何类型，也不能是一对，或者由_ case处理？是否有任何方法来处理任意深度的元组而不将它们转换为其他数据结构，例如变体？

PS：在C中我会通过创建两个模板函数“f”来解决这类问题，一个用于处理元组和另一个类型 .

ocaml type-inference

2 回答

  • 3

    有一种方法可以做到这一点，但由于产生的复杂性，我不建议将它推荐给新用户 . 你应该习惯先写一些常规的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 上的模式匹配如何对应于（类型不佳的）示例函数中的值的模式匹配 .

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

    回复于
  • 5

    元组的任何组合都将具有由其类型完全描述的值形状（因为在类型结构中没有“选择”） - 因此“编译叶子”问题可以在编译时完全静态地回答 . 一旦你有一个在这种类型上运行的功能 - 该功能被修复为仅对该特定类型（和形状）进行操作 .

    如果你想构建一个可以有不同形状的树（但是相同的类型 - 因此可以通过相同的函数处理） - 你需要在混合中添加变体，即经典的 type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree ，或者用某些动态描述值的任何其他类型"choice"形状 .

    回复于

相关问题