functional-programming - 使用 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)中的所有值都大于或等于节点

中存储的值

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

一个 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，如 l eft i 归纳 h 假设)和右子树递归计算。这样构建的树是 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 的结果中投影出 bool 值来定义在上面。

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