0

作为函数式编程 (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)

它返回

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

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

4

1 回答 1

1

你的问题

您的height函数需要一个 type 的值'a gt。当您调用 时height t2，t2是列表的尾部，即 a 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'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)
于 2021-10-03T04:43:49.480 回答