使用 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 的顶层 (utop) 给出警告：

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;;

utop 抛出匹配失败的异常。

我也实现了这个：

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

它returns和

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)

使用 OCaml 查找多路（一般树）的高度

Finding the height of a multiway (general tree) using OCaml

ocaml

multiway-tree

utop