时间戳

首页 > 解决方案 > 如何更改树的类型以返回几乎任何类型的树的正确值？

ocaml - 如何更改树的类型以返回几乎任何类型的树的正确值？

问题描述

我试图找到节点树的最大值，但我遇到了这种错误 This expression has type int bintreebut an expression was expected of type 'a bintree bintree。类型int与类型不兼容'a bintree。

type 'a bintree =
| Nil
| T of 'a bintree * 'a * 'a bintree ;;

let t = T (T (T (Nil, 1, Nil), 2, T (Nil, 3, Nil)), 4, T (T (Nil, 6, Nil), 5, Nil)) ;;

let rec maximum t = 
  match t with
  |Nil -> Nil
  | T (Nil, v, Nil) -> v
  | T (l, v, r) -> max (maximum l) (maximum r) ;;

标签： ocaml

解决方案

您的问题是确定空树的最大值。最大值应该是 type'a但你要返回Nil的是 type 'a bintree。

这实际上是一个有趣的问题。您需要一个适用于任何类型的值。但是真的没有这样的价值。

一种可能性是有一个额外的参数来指定当树为空时要使用的值。对于树中的任何类型，它将表示负无穷大（可能的最小值）。

正如@ThéoWinterhalter 所建议的，另一个（可能更好的）解决方案是让你的函数返回类型'a option。它会None在树为空时返回，Some maxval否则返回。

推荐阅读