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 @?= [] )

If your m type variable was meant to be a MonadPlus instead of just a Monad, you could then return mzero for an Empty tree and also when the key you want cannot be found. Both Maybe and [] are instances of MonadPlus. — jpmarinier
– jpmarinier, Commented Dec 6, 2020 at 16:50

jpmarinier · Accepted Answer · 2020-12-06 22:00:50Z

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

Collectives™ on Stack Overflow

Trying to implement a binary tree search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related