使用 OCAML 中提供的高阶函数检查树是否为 BST

Question

所以让我首先说这是我无法解决的过去作业的一部分，但由于我正在准备测试，所以我想知道如何做。我有导师提供的 map_tree 和 fold_tree 的这些实现：

let rec map_tree (f:'a -> 'b) (t:'a tree) : 'b tree =
match t with
| Leaf x -> Leaf (f x)
| Node (x,lt,rt) -> Node (f x,(map_tree f lt),(map_tree f rt))

let fold_tree (f1:'a->'b) (f2:'a->'b->'b->'b) (t:'a tree) : 'b =
  let rec aux t =
    match t with
     | Leaf x -> f1 x
     | Node (x,lt,rt) -> f2 x (aux lt) (aux rt) 
  in aux t

我需要使用上述函数实现一个验证树是 BST 的函数，到目前为止，这是我已经完成的，但我收到了错误：

 Error: This expression has type bool but an expression was expected of type
     'a tree

这是我的代码：

 let rec smaller_than t n : bool =
 begin match t with
 | Leaf x -> true
 | Node(x,lt,rt) -> (x<n) && (smaller_than lt x) && (smaller_than rt x)
 end

 let rec greater_equal_than t n : bool =
 begin match t with
 | Leaf x -> true
 | Node(x,lt,rt) -> (x>=n) && (greater_equal_than lt x) && (greater_equal_than rt x)
 end

 let check_bst t =
 fold_tree (fun x -> true) (fun x lt rt -> ((check_bst lt) && (check_bst rt)&&(smaller_than lt x)&&(greater_equal_than rt x))) t;;

有什么建议吗？我似乎无法准确理解高阶函数在 OCAML

中的工作原理

Answer 1

BST的规格是多少？这是一棵二叉树，其中：

左子树（也是BST）中的所有元素都严格小于节点存储的值
并且右子树（也是BST）中的所有值都大于或等于节点存储的值

A fold 是一个归纳原则：你必须解释如何处理基本案例（这里的 Leaf 案例）以及如何在步骤案例中组合子案例的结果（这里的 Node 案例）。

A Leaf 始终是 BST 因此基本情况将非常简单。但是，在 Node 的情况下，我们需要确保值位于正确的子树中。为了能够执行此检查，我们将需要额外的信息。这个想法是有一个 fold 计算：

给定的树是否是 BST
及其所有值存在的区间

让我们引入类型同义词来构建我们的想法：

type is_bst      = bool
type 'a interval = 'a * 'a

正如预测的那样，基本情况很简单：

let leaf_bst (a : 'a) : is_bst * 'a interval = (true, (a, a))

在 Node 的情况下，我们将值 a 存储在节点中，并为左侧递归计算结果（lih，如 left induction hypothesis）和右子树。这样构建的树是 BST 当且仅当两个子树是 (b1 && b2) 并且它们的值符合前面描述的属性。这棵新树的值存在的区间现在更大 (lb1, ub2)。

let node_bst (a : 'a) (lih : is_bst * 'a interval) (rih : is_bst * 'a interval) =
  let (b1, (lb1, ub1)) = lih in
  let (b2, (lb2, ub2)) = rih in
  (b1 && b2 && ub1 < a && a <= lb2, (lb1, ub2))

最后，检查树是否为 BST 的函数是通过从调用 fold_tree leaf_bst node_bst 的结果中投影出布尔值来定义的。

let bst (t : 'a tree) : bool =
  fst (fold_tree leaf_bst node_bst t)

使用 OCAML 中提供的高阶函数检查树是否为 BST

Check if a tree is a BST using a provided higher order function in OCAML

ocaml

functional-programming

higher-order-functions

binary-search-tree