144 lines
3.4 KiB
Haskell
144 lines
3.4 KiB
Haskell
module Hasklet1 where






  A generic binary tree with values at internal nodes.


data Tree a = Node a (Tree a) (Tree a)


 Leaf


deriving (Eq,Show)






  Build a balanced binary tree from a list of values.


tree :: [a] > Tree a


tree [] = Leaf


tree (x:xs) = Node x (tree l) (tree r)


where (l,r) = splitAt (length xs `div` 2) xs






 Some example trees containing integers.


t1, t2, t3, t4 :: Tree Int


t1 = Node 1 Leaf (Node 2 Leaf Leaf)


t2 = Node 3 (Node 4 Leaf Leaf) Leaf


t3 = Node 5 t1 t2


t4 = tree (filter odd [1..100])




treeFold :: (a > b > b > b) > b > Tree a > b


treeFold _ b Leaf = b


treeFold f b (Node a t1 t2) = f a (treeFold f b t1) (treeFold f b t2)




 An example tree containing a secret message!


t5 :: Tree Char


t5 = tree " bstyoouu rd oerrvialentikne"






  Define a recursive function that sums the numbers in a tree.





 >>> sumTree Leaf


 0





 >>> sumTree t3


 15





 >>> sumTree t4


 2500





sumTree :: Num a => Tree a > a


sumTree Leaf = 0


sumTree (Node a t1 t2) = a + sumTree t1 + sumTree t2






  Define a recursive function that checks whether a given element is


 contained in a tree.





 >>> contains 57 t4


 True





 >>> contains 58 t4


 False





 >>> contains 'k' t5


 True





 >>> contains 'z' t5


 False





contains :: Eq a => a > Tree a > Bool


contains _ Leaf = False


contains v (Node a t1 t2) = v == a  contains v t1  contains v t2






  Define a function for converting a binary tree of type 'Tree a' into


 a value of type 'b' by folding an accumulator function over the tree.


 You should start by writing a type definition for the function.





 Note there is more than one correct type for this function! Part of your


 task is to figure out the type. For inspiration, think about the types of


 the functions `foldl` and `foldr` for lists.





foldTree :: (a > b > b > b) > b > Tree a > b


foldTree _ b Leaf = b


foldTree f b (Node a t1 t2) = f a (foldTree f b t1) (foldTree f b t2)






  Use 'foldTree' to define a new version of 'sumTree'.





 >>> sumTreeFold Leaf


 0





 >>> sumTreeFold t3


 15





 >>> sumTreeFold t4


 2500





sumTreeFold :: Num a => Tree a > a


sumTreeFold = foldTree ((.(+)).(.).(+)) 0






  Use 'foldTree' to define a new version of 'contains'.





 >>> containsFold 57 t4


 True





 >>> containsFold 58 t4


 False





 >>> containsFold 'v' t5


 True





 >>> containsFold 'q' t5


 False





containsFold :: Eq a => a > Tree a > Bool


containsFold v = foldTree (\a b c > a == v  b  c) False






  Implement a function that returns a list of values contained at each


 level of the tree. That is, it should return a nested list where the


 first list contains the value at the root, the second list contains the


 values at its children, the third list contains the values at the next


 level down the tree, and so on.





 Apply this function to 't5' to reveal the secret message!





 >>> levels Leaf


 []





 >>> levels t1


 [[1],[2]]





 >>> levels t2


 [[3],[4]]





 >>> levels t3


 [[5],[1,3],[2,4]]





 >>> levels (tree [1..10])


 [[1],[2,6],[3,4,7,9],[5,8,10]]





levels :: Tree a > [[a]]


levels = foldTree (\a b c > [a] : padded b c) []


where


padded [] xs = xs


padded xs [] = xs


padded (x:xs) (y:ys) = (x ++ y) : padded xs ys
