使用OCaml查找多路(一般树)的高度

Question

作为一个函数式编程(OCaml)的新手，我一直被这个问题困扰着。

我得到了如下代码:

let rec height tr =
match tr with
| Node(d,[]) -> 1 
| Node(d,[t1]) -> 1 + height t1
| Node(d,[t1;t2]) -> 1 + max (height t1) (height t2)

但是OCaml的顶层给出了一个警告:

Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Node (_, _::_::_::_)

当我运行

let t : int gt =
Node('a',
[Node('b',[]);
Node('c',
[Node('d',
[Node('e',[])]);
Node('f',[]);
Node('g',[])])
]);;
height t;;

top抛出匹配失败异常。

我还实现了这个:

let rec height' tr =
match tr with
| Node(d,[]) -> 1 
| Node(d,_::xs) -> 1 + max (List.map height' xs) 

返回

Line31 |   | Node(d,_::xs) -> 1 + max (List.map height' xs) 
^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type int list -> int list
but an expression was expected of type int

此外，我还尝试了另一种方法:

let rec height tr =
match tr with
| Node(d,[]) -> 1 
| Node(d,[t1]) -> 1 + height t1
| Node(d, t1::t2) -> 
if t2=[]
then 2
else
2 + height t2

则错误为:

Line26 |   2 + height t2 
^^
Error: This expression has type 'a gt list
but an expression was expected of type 'a gt

那么，我该如何克服这个问题呢?

Answer 1

你的问题

您的height函数期望'a gt类型的值。当调用height t2时，t2是列表的尾部，即a gt list。如果你把它传递给height，你会得到一个类型不匹配。

如何处理这个问题

给定树的定义:

type 'a gt = Node of 'a * 'a gt list

写一个height函数很简单，我认为你可能想得太多了，因为你的模式匹配中有很多案例。

对于任何递归，键都是一个基本情况。

let rec height tr =
match
| Node (_, []) -> 1

具有空列表的节点高度为1。树中的实际数据并不重要，因此我们在模式匹配中使用_。

唯一的其他可能是列表不是为空。所以我们可以匹配非空列表。同样，第一个节点不重要。

let rec height tr =
match
| Node (_, []) -> 1
| Node (_, _::xs) -> 2 + ...

现在我们必须将'a gt list转换为int类型。height将把'a gt的值转换为int。那么我为什么不直接映射xs呢?

let rec height tr =
match
| Node (_, []) -> 1
| Node (_, _::xs) -> 2 + List.map height xs

啊，但是这把xs变成了int list，我们不能把它加到int上。我们可以使用fold_left对该列表求和。

let rec height tr =
match
| Node (_, []) -> 1
| Node (_, _::xs) -> 
let sum = List.fold_left (+) 0 in
2 + sum (List.map height xs)

还有一点

使用function关键字，我们可以简化它。

let rec height =
function
| Node (_, []) -> 1
| Node (_, _::xs) -> 
let sum = List.fold_left (+) 0 in
2 + sum (List.map height xs)