REVISED: Wednesday, January 24, 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 hang 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 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>
[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 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>
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 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 article 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.
