FP Laboratory 11

From Marek Běhálek Wiki
Revision as of 12:59, 14 November 2023 by Fai0013 (talk | contribs)
Jump to navigation Jump to search

Binary Trees

  • Create a data type Tree that defines binary tree where values are stored in leaves and also in branches.
data Tree a = Leaf a 
            | Branch a (Tree a) (Tree a) deriving (Show)
  • Prepare an example of a binary tree.
testTree1 :: Tree Int            
testTree1 = Branch 12 (Branch 23 (Leaf 34) (Leaf 45)) (Leaf 55)

testTree2 :: Tree Char            
testTree2 = Branch 'a' (Branch 'b' (Leaf 'c') (Leaf 'd')) (Leaf 'e')
  • Create a function that sums all values stored in the tree.
sum' :: Tree Int -> Int
sum' :: Tree Int -> Int
sum' (Leaf x) = x
sum' (Branch x l r) = sum' l + x + sum' r
  • Create a function that extracts all values from the tree into an list.
toList :: Tree a -> [a]
toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch x l r) = toList l ++ [x] ++ toList r
  • One possibility how to represent a tree in a textual form is a(b(d,e),c(e,f(g,h))). Create functions that are able to read and store a tree in such a notation.
Video logo.png
toString :: Show a => Tree a -> String
fromString :: Read a => String -> Tree a
toString :: Show a => Tree a -> String
toString (Leaf x) = show x
toString (Branch x l r) = show x ++ "(" ++ (toString l) ++ "," ++ (toString r) ++ ")"

fromString :: Read a => String -> Tree a
fromString inp = fst (fromString' inp) where
  fromString' :: Read a => String -> (Tree a,String)
  fromString' inp = 
    let
      before = takeWhile (\x ->  x /='(' &&  x /=',' &&  x/=')') inp 
      after = dropWhile (\x ->  x /='(' &&  x /=',' && x/=')') inp
      value = read before
    in if null after || head after /= '(' then (Leaf value, after) else 
        let
          (l,after') = fromString' (tail after)
          (r,after'') = fromString' (tail after') 
        in (Branch value l r, tail after'')


Additional exercises

  • Create a function that counts all leaves in the tree.
leafCount :: Tree a -> Int
  • Create a function that counts all branches in the tree.
branchCount :: Tree a -> Int
  • Create a function that checks whether a given element is stored in the tree.
contains :: Eq a => Tree a -> a -> Bool
  • Create a function that finds a maximum value stored in the tree.
maxTree :: Ord a => Tree a -> a
  • Create a function that returns a number of elements greater than a given value.
greaterThan :: Ord a => Tree a -> a -> Int
  • Create a function that returns the depth of a tree.
depthTree :: Tree a -> Int
  • Consider the following alternative definition of the binary tree.
data Tree2 a = Null | Branch a (Tree2 a) (Tree2 a)
  • Is this definition equivalent to the previous one? If not, explain why and give an example of a tree that can be constructed with the first definition but not with the second one or vice versa.
  • Implement all functions above adjusted for the alternative definition of the binary tree.
  • Consider the following definition and the example of the m-ary tree.
data MTree a = MTree a [MTree a]
testTree1 :: MTree Int            
testTree1 = MTree 1 [(MTree 2 [(MTree 3 []),(MTree 4 [(MTree 5 []),(MTree 6 [])]), (MTree 7 []),(MTree 8 [])]), (MTree 9 [])]
  • Create a function that sums all values stored in the m-ary tree.
msum :: MTree Int -> Int
  • Create a function that extracts all values from the m-ary tree into a list.
mToList :: MTree a -> [a]