2021-04-17 02:40:32 -07:00

 ```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 ```