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

Question

So let me start by saying that this was part of the past homework that I could not solve, but as I prepare for the test, I would like to know how to do it. I have these map_tree and fold_tree implementations provided by the instructor:

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

I need to implement a function that checks that the tree is BST using the above functions, so far this is what I did and I get the error:

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

This is my code:

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

Any suggestions? It seems to me hard to understand how higher order functions work in OCAML

Answer 1

BST? , :

• ( BST) , node
• ( BST) , node

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, node, , (lih l eft i nduction h ypothesis) . , 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)