OCaml

Question

我有 2 种树：

type ref_tree = Node of int * ref_tree list ref
type tree = Node of int * tree list

我想编写一个函数 convert: ref_tree -> tree，它获取包含邻居的树作为包含它们的列表的引用，并输出一棵树，其中引用更改为普通列表。这是我尝试过的：

let rec convert t =
        match t with
        | Node (x, l) ->
            if (!l = []) then Node (x, []) else
            Node (x, (List.map convert !l))

但是 OCaml returns 尝试编译时出错：

if (!l = []) then Node (x, []) else
Error: This expression has type 'a list
       but an expression was expected of type tree list ref

其中 This expression 指向 Node (x, []) 内的空列表。为什么类型不匹配？

Answer 1

编译器混淆了你的两个 Node 构造函数（ref_tree 之一和 tree 之一）。您可以通过多种方式帮助它，包括：

let rec convert t =
  match (t : ref_tree) with
  | Node (x, l) ->
     if (!l = []) then Node (x, []) else
       Node (x, (List.map convert !l))

Answer 2

这里的问题是您定义了两个构造函数 Node，第二个定义 (type tree = Node of …) 隐藏了第一个。

这意味着当您匹配 t 并将其解构为 Node(x, l)，OCaml 将其视为 tree，而不是 ref_tree（因此将 l 视为 tree list 而不是 ref_tree list ref )

解决此问题的一种方法是更改 ref_tree 构造函数：

# type ref_tree = Ref_node of int * ref_tree list ref;;
type ref_tree = Ref_node of int * ref_tree list ref

# let rec convert t =
          match t with
          | Ref_node (x, l) ->
              if (!l = []) then Node (x, []) else
              Node (x, (List.map convert !l));;
val convert : ref_tree -> tree = <fun>

（另一种方法是在模块 Tree 和 RefTree 中定义这些类型并使用 Tree.Node 和 RefTree.Node）

OCaml - 转换树与普通树的引用

OCaml - converting trees with references to normal trees

tree