Trying to implement a binary tree search

Question

Im trying to implement a Binary Tree Search algorithm in haskell.

data BinTree k d = 
   Branch (BinTree k d) (BinTree k d) k d 
  | Leaf k d 
  | Empty
  deriving (Eq, Show)

is the data structure im using to capture my binary tree. The problem is I dont know what to return if we cant find the value. This is what I have so far for my search function :

lkp :: (Monad m, Ord k) => BinTree k d -> k -> m d
lkp (Leaf a b) x
  | a == x = return(b)
lkp (Branch lSub rSub a b) x
  | a < x = lkp rSub x
  | a > x = lkp lSub x
  | a == x = return(b)

I can see in the tests that the test expects a return value of [] back yet I cannot understand how we return this empty value. This is an example of one of those tests :

testCase "3 in Leaf 5 500 ([]))[1 mark]"
    (lkp (Leaf 5 500) 3 @?= [] ) 

Answer 1

So we miss a way to return a “zero” or “empty” value.

Fortunately, the Haskell base library (Prelude) offers the MonadPlus class. MonadPlus is a specialized version of Monad, which augments the regular Monad interface with mzero and mplus, providing essentially a monoid-like structure. Theory here on the Haskell Wiki.

Using MonadPlus, the code for lkp can be written as follows:

import Control.Monad

data BinTree k d = 
       Branch (BinTree k d) (BinTree k d) k d 
    |  Leaf k d 
    |  Empty
  deriving (Eq, Show)

lkp :: (MonadPlus m, Ord k) => BinTree k d -> k -> m d
lkp (Branch lSub rSub a b) x
  | a < x      =  lkp rSub x
  | a > x      =  lkp lSub x
  | otherwise  =  return b
lkp (Leaf a b) x  =  if (a == x)  then  (return b)  else  mzero
lkp Empty      _  =  mzero

Note:: I am using the otherwise keyword instead of the equality test in order to silence a spurious “non-exhaustive patterns” warning.

Testing under ghci:

 λ> 
 λ> :load q65169028.hs
[1 of 1] Compiling Main             ( q65169028.hs, interpreted )
Ok, one module loaded.
 λ> 
 λ> tr1 = Branch (Leaf 1 2) (Branch (Leaf 5 6) (Branch (Leaf 9 10) (Leaf 17 18) 13 14) 7 8) 3 4
 λ> 
 λ> (lkp tr1 7) :: [Int]
[8]
 λ> 
 λ> (lkp tr1 8) :: [Int]
[]
 λ> 
 λ> (lkp tr1 17) :: [Int]
[18]
 λ> 

We want to force the interpreter to choose lists as our MonadPlus instance, hence the :: [Int] type signature at the end of each line.

If that sounds too cumbersome, it is always possible the specialize the lkp function further, like this:

llkp :: Ord k => BinTree k d -> k -> [d]
llkp tr x = lkp tr x