CODEWITHSUNDEEP
haskellsearchbinary-tree
Dipesh Desai
Dipesh Desai

Reputation: 114

Searching a Value in Binary tree haskell

I have just started learning Haskell and I am trying to write a code for searching for a particular value in a binary tree and if present return true else false This is how my tree structure looks like

data Tree = Leaf Int | Node Tree Int Tree

I am not sure how to proceed with the function to traverse through the tree and return the value. I did try BFS and DFS but I am not sure on how to return once I have got my value.

An example of how my function should look

Search 5 (Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9)))

Upvotes: 3

Views: 5364

Answers (2)

Regis Kuckaertz
Regis Kuckaertz

Reputation: 991

I am not sure how to proceed with the function to traverse through the tree and return the value.

From that sentence, I understand you would have no problem writing a traversal yourself, but that there is a mental leap you need to take to understand how Haskell works.

You see, you never return anything in Haskell. Returning is fundamentally an imperative statement. Haskell is a declarative language, which means that writing programs is done by stating facts. That nuance can be discomforting, especially if you've been introduced to programming through learning imperative languages like C, Java, JavaScript, etc. But once you truly understand it, you will see how much more expressive and easy declarative programming is.

Because of its strong mathematical roots, in Haskell facts are stated in the form of equations, i.e. expressions where the = sign literally means the left- and right-hand side are equal (whereas in an imperative language, it would probably mean that you assign a value to a variable -- that does not exist in Haskell).

The program @Haleemur Ali wrote is in 1:1 correspondence with how you would write search using math notation:

search(x, t) = { x == y       if t = Leaf y
               , true         if t = Node l y r and x == y
               , search(x, l) if t = Node l y r and x < y
               , search(x, r) if t = Node l y r and x > y
               }

Indeed many times, at least as a beginner, writing Haskell is just a matter of translation, from math notation to Haskell notation. Another interpretation of Haskell programs is as proofs of theorems. Your search is a theorem saying that "if you have a tree and an integer, you can always tell if the integer is somewhere inside the tree". That's what you are telling the compiler when you write a function signature:

search :: Int -> Tree -> Bool

The compiler will only be happy if you write a proof for that theorem ... you probably guessed that the algorithm above is the proof.

An interesting observation is that the algorithm is almost dictated by the shape of the data type. Imagine you wanted to sum all the values in a tree instead:

sum(t) = { x                   if t = Leaf x
         , x + sum(l) + sum(r) if t = Node l x r
         }

Every time you want to write an algorithm over a binary tree, you will write something like the above. That is fairly mechanical and repetitive. What if later on you expand your program to deal with rose trees? Tries? You don't want to write the same algorithms and take the risk of making a mistake. One would try to come up with a function that walks down a tree and combines its values (using Haskell notation from now on):

walk :: (Int -> b) -> (b -> b -> b) -> Tree -> b
walk f g (Leaf x) = f x
walk f g (Node l x r) =
  let a = walk f g l
      b = walk f g r
  in g (g (f x) a) b

With this function alone, you can write all manners of traversals on trees:

sum t      = walk id (+) t
search x t = walk (== x) (||) t

walk is such a recurring pattern that it has been abstracted. All the data structures that expose the same pattern of recursion are said to be foldable, and the implementation is often so obvious that you can ask the compiler to write it for you, like so:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Foldable)

There's even a definition of sum for any foldable data structure.

Upvotes: 2

Haleemur Ali
Haleemur Ali

Reputation: 28243

A binary search could be written as follows. The type can be more generic, as we only need the items to be orderable to store / search in a binary tree.

We visit each node and either return true, or search in 1 of the child nodes.

example Node

   5
 /   \
3     7

lets search for 7.

We first visit the root. since 5 != 7, we test a child node. Since 7 > 5, we search in the right node, since 7 cannot appear in the left child (all values guaranteed to be lower than 5 on the left child)

If we reach a leaf, we just check if it contains the search term.

search :: Ord a => a -> BinaryTree a -> Bool
search a (Leaf b) = compare a b == EQ
search a (Node left b right) 
  case compare a b of 
    EQ -> True
    LT -> search a left
    GT -> search a right

Upvotes: 4

Related Questions