如何使用递归类型

Question

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

所以我定义：

1. 树类型，我将其定义为 type tree = [] | Intlist of int list | Treelist of tree list;;

2. 求和函数，例如

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

我尝试编译时遇到的错误是这样的：

错误：此表达式具有树列表类型，但表达式应为树类型

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

怎么了？函数还是我对树的定义？

Answer 1

看看这个表达式：

(sum_list head) + (sum_list tail)

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

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

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

您的定义tree是可以的（尽管重新定义是有风险的[]，因为您可能需要在代码中的其他位置使用其通常的类型）。