Haskebook Chapter 11 tree

Chapter11Tree.hs

module Chapter11Tree where

data OperatingSystem = Linux
                     | OpenBSD
                     | Mac
                     | Windows
                     deriving (Eq, Show)
                     
data ProgrammingLanguage = Haskell
                         | Agda
                         | Idris
                         | PureScript
                         deriving (Eq, Show)
                         
data Programmer = Programmer
  { os :: OperatingSystem
  , lang :: ProgrammingLanguage
  } deriving (Eq, Show)
  
allOperatingSystems :: [OperatingSystem]
allOperatingSystems = [Linux, OpenBSD, Mac, Windows]

allLanguages :: [ProgrammingLanguage]
allLanguages = [Haskell, Agda, Idris, PureScript]

allProgrammers :: [Programmer]
allProgrammers = [Programmer os lang | os <- allOperatingSystems, lang <- allLanguages]

data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving (Eq, Ord, Show)

insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b n@(Node left a right)
  | b == a = n
  | b < a  = Node (insert' b left) a right
  | b > a  = Node left a (insert' b right)

mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) =
  Node (mapTree f left) (f a) (mapTree f right)

preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left a right) = a : preorder left ++ preorder right

inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder (Node left a right) = inorder left ++ [a] ++ inorder right

postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left a right) = postorder left ++ postorder right ++ [a]

testTree :: BinaryTree Integer
testTree = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)

-- i think this is the only ay to do this
-- if you try to pattern match you end up with multiple b's
-- but no function to merge them.
foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree f acc tree = foldr f acc $ inorder tree