CODEWITHSUNDEEP
functional-programmingocamlbinary-search-treehigher-order-functions
AndresGalaviz
AndresGalaviz

Reputation: 153

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

So let me start by saying this was part of a past homework I couldn't solve but as I am preparing for a test I would like to know how to do this. I have these implementations of map_tree and fold_tree 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 verifies a tree is a BST using the above functions, so far this is what I've accomplished and I'm getting 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? I seem to have trouble understanding exactly how higher order functions work in OCAML

Upvotes: 4

Views: 2909

Answers (1)

gallais
gallais

Reputation: 12103

What is the specification of a BST? It's a binary tree where:

  • all the elements in the left subtree (which is also a BST) are strictly smaller than the value stored at the node
  • and all the ones in the right subtree (which is also a BST) are bigger or equal than the value stored at the node

A fold is an induction principle: you have to explain how to deal with the base cases (the Leaf case here) and how to combine the results for the subcases in the step cases (the Node case here).

A Leaf is always a BST so the base case is going to be pretty simple. However, in the Node case, we need to make sure that the values are in the right subtrees. To be able to perform this check, we are going to need extra information. The idea is to have a fold computing:

  • whether the given tree is a BST
  • and the interval in which all of its values live

Let's introduce type synonyms to structure our thoughts:

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

As predicted, the base case is easy:

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

In the Node case, we have the value a stored at the node and the results computed recursively for the left (lih as in left induction hypothesis) and right subtrees respectively. The tree thus built is a BST if and only if the two subtrees are (b1 && b2) and their values respect the properties described earlier. The interval in which this new tree's values live is now the larger (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))

Finally, the function checking whether a tree is a BST is defined by projecting out the boolean out of the result of calling fold_tree leaf_bst node_bst on it.

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

Upvotes: 6

Related Questions