HASKELL RECURSIVE DATA STRUCTURE TREE EXAMPLES

REVISED: Wednesday, October 9, 2024

1. INTRODUCTION

To learn how to code a recursive data structure tree start with the following three basic definitions: 

-- Firstly, the basic definition of a Tree.
data Tree a = Leaf a | Branch (Tree a) (Tree a)
   deriving (Eq, Show)

A Tree a is either a leaf, containing a value of type a or a branch, from which hangs two other trees of type Tree a.

-- Secondly, the basic definition of map for lists.
map              :: (a -> b) -> [a] -> [b]
map       _ [] = []
map f (x:xs) = f x : map f xs

-- Thirdly, the basic definition of foldr for lists.
foldr                 :: (a -> b -> b) -> b -> [a] -> b
foldr       f z []  = z
foldr f z (x:xs) = f x (foldr f z xs)

2. RECURSIVE DATA STRUCTURE TREE EXAMPLE 1

For details regarding this Example 1 code please refer to the following link.

Module 1:

module RDST1 where

import Prelude hiding (map, foldr)

data Tree a = Leaf a | Branch (Tree a) (Tree a)
   deriving (Eq, Show)

-- The basic map definition for a list is used to write the basic map definition for a tree. 
treeMap                       :: (a -> b) -> Tree a -> Tree b
treeMap                    f  = g where
   g                 (Leaf x) = Leaf (f x)
   g (Branch left right) = Branch (g left) (g right)

-- The basic foldr definition for a list is used to write the basic fold definition for a tree. 
treeFold                      :: (b -> b -> b) -> (a -> b) -> Tree a -> b
treeFold fbranch fleaf = g where g (Leaf x) = fleaf x
                                       g (Branch left right) = fbranch (g left) (g right)
 
tree1 :: Tree Integer
tree1 = Branch (Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Branch (Leaf 5) (Leaf 6)))) (Branch (Branch (Leaf 7) (Leaf 8)) (Leaf 9))

tree2 :: Tree Integer
tree2 = Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))

-- Doubles each value in tree.
doubleTree = treeMap (*2)

-- Sum of the Leaf values in tree.
sumTree = treeFold (+) id 

-- List of the Leaves of a tree.
fringeTree = treeFold (++) (: [])

main = do
    putStrLn $ "Original tree1: " ++ (show tree1)
    putStrLn $ "Original tree2: " ++ (show tree2)

GHCi:

Prelude>  :load RDST1
[1 of 1] Compiling RDST1              (RDST1.hs, interpreted )
Ok, modules loaded: RDST1.
Prelude>

Prelude>  main
Original tree1: Branch (Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Branch (Leaf 4) (Branch (Leaf 5) (Leaf 6)))) (Branch (Branch (Leaf 7) (Leaf 8)) (Leaf 9))
Original tree2: Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))
Prelude>

Prelude>  sumTree tree1
45
Prelude>

Prelude>  doubleTree tree1 
Branch (Branch (Branch (Leaf 2) (Branch (Leaf 4) (Leaf 6))) (Branch (Leaf 8) (Branch (Leaf 10) (Leaf 12)))) (Branch (Branch (Leaf 14) (Leaf 16)) (Leaf 18))
Prelude>

Prelude>  fringeTree tree1
[1,2,3,4,5,6,7,8,9]
Prelude>

Prelude>  fringeTree tree2
[1,2,3,4]
Prelude>

Prelude>  let tree3 = doubleTree tree1
Prelude>

Prelude>  tree3
Branch (Branch (Branch (Leaf 2) (Branch (Leaf 4) (Leaf 6))) (Branch (Leaf 8) (Branch (Leaf 10) (Leaf 12)))) (Branch (Branch (Leaf 14) (Leaf 16)) (Leaf 18))
Prelude>

Prelude>  fringeTree tree3
[2,4,6,8,10,12,14,16,18]
Prelude>

3. RECURSIVE DATA STRUCTURE TREE EXAMPLE 2

For details regarding this Example 2 code please refer to the following link.

Module 2:

module RDST2 where

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)
              deriving (Eq,Ord,Show,Read)

main :: IO ()
main  =
   do
      putStrLn "Begin program"

      let aMyTree = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
      print aMyTree
      print (sumMyTree aMyTree)

      let bMyTree = MyFilledNode "r" (MyFilledNode "s" MyEmptyNode MyEmptyNode) (MyFilledNode "a" MyEmptyNode MyEmptyNode)
      print bMyTree

      putStrLn "End program"

sumMyTree                                       :: Num a => MyTree a -> a
sumMyTree MyEmptyNode             = 0
sumMyTree (MyFilledNode n t1 t2) = n + sumMyTree t1 + sumMyTree t2

GHCi:

Prelude>  :load RDST2
[1 of 1] Compiling RDST2              (RDST2.hs, interpreted )
Ok, modules loaded: RDST2.
Prelude>

Prelude>  main
Begin program
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
10
MyFilledNode "r" (MyFilledNode "s" MyEmptyNode MyEmptyNode) (MyFilledNode "a" MyEmptyNode MyEmptyNode)
End program
Prelude>

4. RECURSIVE DATA STRUCTURE TREE EXAMPLE 3

For details regarding this Example 3 code please refer to the following link.

Module 3:

module RDST3 where

import Control.Applicative

data MyTree a = MyNode a [MyTree a]
                deriving (Show)

instance Functor MyTree where
   fmap f (MyNode x treeList) = MyNode (f x) (map (fmap f) treeList)

instance Applicative MyTree where
   pure x = MyNode x []
   (MyNode f treeFunctionList) <*> (MyNode x treeElementList) =
      MyNode (f x) ( (map (fmap f) treeElementList) ++ (map (<*> (MyNode x treeElementList)) treeFunctionList) )

instance Monad MyTree where
   return x = MyNode x []
   MyNode x treeList >>= f = MyNode x' (treeList' ++ map (>>= f) treeList)
      where MyNode x' treeList' = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode 5 [MyNode 3 [], MyNode 2 []]
      print tree1

      let tree2 = MyNode "ABC" [MyNode "DEFG" [], MyNode "HIJKL" []]
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyNode (*2) []) <*> tree1)
      print ((MyNode (*2) [MyNode (+100) [], MyNode (+1000) []]) <*> tree1)
      print ((MyNode init []) <*> tree2)
      print ((MyNode init [MyNode reverse [MyNode tail []]]) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyNode (x+200) []))
      print (tree2 >>= (\x -> MyNode (tail x) []))

      putStrLn "Program ends."

GHCi:

Prelude>  :load RDST3
[1 of 1] Compiling Main             ( RDST3.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  main
Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode 5 [MyNode 3 [],MyNode 2 []]
MyNode "ABC" [MyNode "DEFG" [],MyNode "HIJKL" []]
Tests that prove that MyTree behaves as a Functor.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 3 [MyNode 4 [],MyNode 5 []]
Tests that prove that MyTree behaves as an Applicative.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 10 [MyNode 6 [],MyNode 4 [],MyNode 105 [MyNode 103 [],MyNode 102 []],MyNode 1005 [MyNode 1003 [],MyNode 1002 []]]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" []]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" [],MyNode "CBA" [MyNode "GFED" [],MyNode "LKJIH" [],MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]]]
Tests that prove that MyTree behaves as a Monad.
MyNode 205 [MyNode 203 [],MyNode 202 []]
MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]
Program ends.
Prelude> 

5. CONCLUSION

The purpose of this tutorial is not to discuss the code but to point out you should always start with the basic things you know about Haskell in order to understand the things you think are difficult. Learn the basic concepts they are the building blocks for understanding Haskell.

6. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

HASKELL RECURSIVE BINARY SEARCH TREE

REVISED: Wednesday, January 24, 2024

Haskell Recursive Binary Search Tree.

I. DEFINITIONS

A. BINARY TREE 

A binary tree is a data structure that has a single root node; each node in the tree is either a leaf or a branch. If it is a leaf, it holds a value; if it is a branch, it holds a value and a left child and a right child. Each of these children is another node.

B. COMPLETE BINARY TREE

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

C. HEIGHT OF A BINARY TREE

The height of a binary tree is the length of a path from the root to the deepest node. For example, the height of a tree with a single node is 0; the height of a tree with three nodes, whose root has two children, is 1; and so on. 

D. INTERNAL NODES

Internal nodes have a parent, a root node is not an internal node, and internal nodes have at least one child.

E. LEAF NODES

Leaf nodes have a parent, but no children.

F. PERFECT BINARY TREE

A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.

To determine if a tree is perfect, iterate through the tree, noting its depth and counting the number of leaves, where a tree with one node has a depth of 1. If you have 2^(d-1) leaves then your tree is perfect.

By the definition of complete, a tree can be complete but not perfect, but because a perfect tree is a complete tree that has the entire deepest level filled, any tree that is perfect must be complete.

G. ROOT

A root is the topmost node in a tree. It is a kind of main node in the tree, because all other nodes can be reached from the root. Root has no parent. Root is the node, at which operations on the tree begin.

II.  HASKELL RED-BLACK TREE AND AVL TREE

Defined below  is a polymorphic Binary Tree of as which is either a Leaf which holds an a, or it is a Branch with a left child, which is a Binary Tree of as, a node value, which is an a, and a right child, which is also a Binary Tree of as.

Prelude> data Tree a = Leaf a | Branch (Tree a) a (Tree a)

data Tree a = Leaf a | Branch (Tree a) a (Tree a)
Prelude>

Tree is a type constructor; Branch and Leaf are data constructors. The above declaration defines the following types for Branch and Leaf:

Prelude> :type Branch

Branch :: Tree a -> a -> Tree a -> Tree a

Prelude>

Prelude> :type Leaf

Leaf :: a -> Tree a

Prelude>

Values are stored at each node, with smaller values to the left, greater to the right.

Using the typeclass concept the names of abstract types start with a lowercase letter, and names of concrete types start with an uppercase letter.

A. RED-BLACK TREE

Red-Black tree was invented in 1972 by Rudolf Bayer who called them symmetric binary B-trees.

Red-Black trees are binary search trees in which all nodes are assigned a color as an extra attribute, either red or black. The leaves are considered black.

A Red-Black tree must satisfy these four properties:

1. The root is black

2. All leaves are black.

3. Red nodes can only have black children.

4. All paths from a node to its leaves contain the same number of black nodes.

B. AVL TREE

The AVL tree is named after its inventors, Adelson-Velskii and Landis in 1962.

An AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node differ by at most one, otherwise known as height-balanced.

III. HASKELL RECURSIVE BINARY SEARCH TREE (BST)

Building a balanced binary tree from a list.

Use your text editor to save BalancedTree.hs shown below, to your working directory:

module BalancedTree where

data Tree a = Leaf
            | Node Integer (Tree a) a (Tree a)
            deriving (Show, Eq)

foldTree :: [a] -> Tree a
foldTree = foldr (\x tree -> insertInTree x tree) Leaf

insertInTree :: a -> Tree a -> Tree a
insertInTree x Leaf = Node 0 (Leaf) x (Leaf)
insertInTree x (Node n t1 val t2) = if h1 < h2 
                                    then Node (h2+1) (insertInTree x t1) val t2 
                                    else Node (h1+1) t1 val (insertInTree x t2) 
  where h1 = heightTree t1
             h2 = heightTree t2

heightTree :: Tree a -> Integer
heightTree Leaf = 0
heightTree (Node n t1 val t2) = n

Load the above BalancedTree.hs file into GHCi:

Prelude>  :load BalancedTree.hs
[1 of 1] Compiling Main             ( BalancedTree.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Call the foldTree function, in GHCi:

Prelude>  foldTree "ABCDEFGHIJ"
Node 3 (Node 2 (Node 0 Leaf 'B' Leaf) 'G' (Node 1 Leaf 'F' (Node 0 Leaf 'C' Leaf))) 'J' (Node 2 (Node 1 Leaf 'D' (Node 0 Leaf 'A' Leaf)) 'I' (Node 1 Leaf 'H' (Node 0 Leaf 'E' Leaf)))
Prelude>  

IV. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

In this tutorial, you have received an introduction to the Haskell recursive binary tree.