如何使用递归类型

Question

我需要一个递归地求和树中所有数字的函数。

所以我定义了：

树型，我定义为 type tree = [] | Intlist of int list | Treelist of tree list;;
求和函数，如

let rec sum_list list = 
  match list with  
    Treelist (head::tail) -> (sum_list head) + (sum_list tail) 
  | Intlist (head::tail)  -> head + (sum_list tail) 
  | []                    -> 0

The error I get on trying to compile this is this:

Error: This expression has type tree list but an expression was expected of type tree

指的是Treelist子句中的第二个sumlist。对我来说，树列表类型的表达式似乎应该是树类型。

怎么了？树的功能还是我的定义？

Answer 1

看看这个表达式：

(sum_list head) + (sum_list tail)

头部的类型是tree，但尾部的类型是tree list。所以它们不能都是 sum_list 函数的适当参数。这就是编译器告诉你的。

稍后在您的代码中，您还将 sum_list 应用于整数列表。

OCaml 是一种强类型语言。您不能拥有接受不同类型参数（tree、tree list、int list）的函数。您很可能需要三个不同的函数，每种函数一个。

您对 tree 的定义没问题（尽管重新定义 [] 是有风险的，因为您可能会在代码的其他地方使用它的常用类型）。

Answer 2

首先，学习OCaml时最好不要在类型定义中使用[]构造函数。使用此 [] 构造函数仅在定义替代列表类型（例如使用 GADT）时有用，并且通过这样做它会隐藏通常列表类型中通常的 [] 构造函数。

因此我们在树的定义中将其替换为Empty：

type tree =
| Empty
| Intlist of int list 
| Treelist of tree list

其次，听起来您可能误读了

中 TreeList 的定义

type tree =
| Empty
| Intlist of int list 
| Treelist of tree list

这个定义并不是说list的树就是树。这意味着可以通过在列表树上应用构造函数 TreeList 来构建树：

let treelist (x:tree list): tree = TreeList x

因此在

let rec sum_list list = match list with
  | Treelist (head::tail) -> sum_list head + sum_list tail
  | Intlist (head :: tail) -> head + sum_list tail
  | Empty -> 0

类型检查器正确地抱怨 tail 不是树，而是树的列表。包含树列表 tail 的树将是 TreeList tail。 IntList 的情况也是如此，tail 不是树而是整数列表，包含整数列表 tail 的树将是 IntList tail .

如何使用递归类型

How to use recursive types

ocaml