Haskell is a functional programming language. It is a type of programming paradigm where the focus is on changing data through expressions that don’t have side effects. These expressions are often called pure functions. Let’s see how we can implement a pure function, which inserts an element in a binary search tree (BST).
The most intuitive way to insert an element in a BST is by using recursion. We use the following algorithm for recursion:
root
node.root
key, then we recurse at the left
subtree. Otherwise, we recurse at the right
subtree. When the tree ends, the function inserts at the left (if the inserted key is less than the current key), and vice versa.data Tree a = Nil | Node (Tree a) (Tree a) aindentation:: Int-> Stringindentation = \indents ->case indents of0 -> ""1 -> "+---"_ -> "| " ++ indentation (indents-1)printTree:: Show a => Tree a -> Int -> StringprintTree = \tree -> \level ->case tree ofNil -> ""Node Nil Nil b -> (show b)Node left Nil b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree left (level+1))Node Nil right b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree right (level+1))Node left right b -> (show b) ++ "\n" ++ indentation (level) ++ (printTree left (level+1)) ++ "\n" ++ indentation (level) ++ (printTree right (level+1))instance Show a => Show (Tree a) whereshow = \tree ->printTree tree 1insert :: Ord a => Tree (a,b) -> (a,b) -> Tree (a,b)insert = \tree -> \(x,y) ->case tree ofNil -> Node Nil Nil (x,y) -- if empty, then insert rootNode left right (a,b) | x < a -> Node (insert left (x,y)) right (a,b)| otherwise -> Node left (insert right (x,y)) (a,b)main = print (insert (insert (insert (insert Nil (7, "Seven")) (8, "Eight")) (6, "Six")) (5, "Five"))
In the code given above:
In line 1, we define the datatype Tree
, which can either be an empty tree or a node that contains two subtrees and a value. As we can infer, Nil
represents an empty tree, and a Node
contains two subtrees of type Tree
and a value whose type will be determined on function invocation.
For the sake of simplicity, we do not need to concern ourselves with the internal workings of indentation
and printTree
. Their purpose is to neatly print the tree when we use the insert
function.
In lines 18–21, we make Tree
an instance of the Show
type class, by defining the show
function that takes a Tree
and returns a string
.
We consider a tree that contains a tuple of key-value pairs such that the tree is organized as a binary search tree based on the key value. A binary search tree stores all the keys that are less than the one in the root
in the left
subtree and stores the rest in the right
subtree. We insert new values in the tree, according to these above constraints.
In line 23, Ord a => Tree (a,b) -> (a,b) -> Tree (a,b)
is the type annotation for our insert
function. Haskell is statically typed, and every function or variable has a type. In this case, insert
is a function that takes a Tree
and a tuple, and returns a Tree
(the tree with a newly inserted value). The Ord a
ensures that the first element of the tuple should be of a totally ordered datatype.
Next, in line 24, we have the function definition, which shows that our function takes a Tree
, a tuple (x,y)
, and a case
expression on Tree
that implements our recursive formulation of the problem.
In line 26, The first equation tells that if the Tree
is Nil
, then this means that it is an empty tree and we need to insert the root
of the tree. Hence, we return Node Nil Nil (x,y)
.
In line 27, The second equation solves the general case. We have a Tree
which is a Node
with left
and right
subtrees and a key-value pair (x,y)
. If the key to be inserted, a
, is less than x
, then we return the tree where the recursive function is called at the left
subtree. Otherwise, we recurse at the right
subtree.
Finally, in line 29, we generate the whole tree by invoking our insert
function and calling the printTree
function to print the final tree.