Trees
Consider the following Binary Tree type
data Tree a = Leaf | Node (Tree a) a (Tree a)1 inClass
Write the function elemTree that tests if an element x occurs in a
binary search tree of type Tree a.
elemTree :: Ord a => a -> Tree a -> Bool
elemTree q t = succOf q t == q
-- or directly:
elemTree :: Ord a => a -> Tree a -> Bool
elemTree _ Leaf = False
elemTree q (Node l x r) | q < x = elemTree q l
| q == x = True
| otherwise = elemTree q r2 atHome
Write functions that return all values of type a in a tree of type
Tree a in depth-first (pre-order), depth-first (in-order), and
breadth-first order.
traverseTree :: ([a] -> a -> [a] -> [a]) -> Tree a -> [a]
traverseTree _ Leaf = []
traverseTree combine (Node l x r) =
combine (traverseTree combine l) x (traverseTree combine r)
preOrderTraversal :: Tree a -> [a]
preOrderTraversal = traverseTree (\l x r -> x : (l ++ r))
inOrderTraversal :: Tree a -> [a]
inOrderTraversal = traverseTree (\l x r -> l ++ (x : r))3 atHome
Write a function showTree that gives a nice representation as a
String for a given tree. Every leaf should be placed on a different
line (separated by "\n"). Leaves that are deeper in the tree should
be further to the right than leaves higher in the tree.
4 inClass
Write a function mapTree and a function foldTree that work on a
Tree, analoguous to map and foldr on lists. Also give the type
of these functions.
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Leaf = Leaf
mapTree f (Node l x r) = Node (mapTree f l) (f x) (mapTree f r)
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ z Leaf = z
foldTree f z (Node l x r) = f (foldTree f z l) x (foldTree f z r)5 inClass
Write a function height, that computes the amount of levels in a
Tree. Give a definition using recursion, and a different definition
using foldTree.
height = foldTree (\l _ r -> 1 + l `max` r) 16 atHome
Suppose that a tree t has height n. What is the minimal and
maximal amount of leaves that t could have?
7 atHome
Write a function that computes all paths of type [a] from the root
up to a leaf for a tree of type Tree a.
paths :: Tree a -> [[a]]
paths Leaf = [[]]
paths (Node l x r) = map (x:) (paths l) ++ map (x:) (paths r)8 atHome
Write a function that computes a list of nodes that occur on one of the longest paths from the root up to a leaf. Try to keep the solution linear with respect to the size of the tree.
9 atHome
Write mapTree using foldTree
mapTree f = foldTree (\l x r -> Node l (f x) r) Leaf10 inClass
Write a function extractMin that removes the smallest element from a
binary search tree. Returns the smallest element and the remainder of
the tree.
extractMin :: Tree a -> Maybe (a, Tree a)
extractMin Leaf = Nothing
extractMin (Node l k r) = case extractMin l of
Nothing -> Just (k, r)
Just (m,l') -> Just (m, Node l' k r)11 inClass
Write a function delete that deletes an element from the tree. You
can assume the element appears at most once. Your new tree should
remain a binary search tree.
Hint: You may want to use the function extractMin you defined above.
delete :: Ord a => a -> Tree a -> Tree a
delete _ Leaf = Leaf
delete x (Node l k r) = case x `compare` k of
LT -> Node (delete x l) k r
EQ -> case extractMin r of
Nothing -> l
Just (m,r') -> Node l m r'
-- we replace k by its successor.
GT -> Node l k (delete x r)12 inClass
Define a binary tree type LeafTree in which leaves store values of
type a and internal nodes store values of type b
data LeafTree a b = Leaf a
| Node (LeafTree a b) b (LeafTree a b)
deriving (Show,Eq)13 atHome
Define a function height that given a LeafTree computes the height of
the LeafTree a b. Leaves have height one.
height :: LeafTree a b -> Int
height (Leaf _) = 1
height (Node l _ r) = 1 + max (height l) (height r)14 inClass
Define a function annotate, that given a LeafTree Int b labels every
internal node with the minimum and maximum value appearing in the
leaves in its subtree.
e.g.
Node (Node (Leaf 3) "left" (Leaf 5))
"root"
(Leaf 1)
->
Node (Node (Leaf 3) (3,5) (Leaf 5))
(1,5)
(Leaf 1)annotate :: LeafTree Int b -> LeafTree Int (Int,Int)
annotate t = case annotate' t of
(t',_,_) -> t'
-- | Computes the annotated tree, as well as the minimum and maximum in the tree
annotate' :: LeafTree Int b -> (LeafTree Int (Int,Int), Int, Int)
annotate' (Leaf x) = (Leaf x, x, x)
annotate' (Node l _ r) = let (l',lmin,lmax) = annotate' l
(r',rmin,rmax) = annotate' r
mi = min lmin rmin
ma = max lmax rmax
in (Node l' (mi,ma) r', mi, ma)15 atHome
Write a function withDepth that annotates the tree by its depth. The
depth of a node v is the length of the path from the root to v.
withDepth :: LeafTree a b -> LeafTree (a,Int) (b,Int)
withDepth = withDepth' 0
withDepth' :: Int -> LeafTree a b -> LeafTree (a,Int) (b,Int)
withDepth' d (Leaf x) = Leaf (x,d)
withDepth' d (Node l x r) = Node (withDepth' (d+1) l) (x,d) (withDepth' (d+1) r)16 atHome
Write a function trimWhen :: (a -> Bool) -> (b -> Bool) -> LeafTree a b
-> LeafTree (LeafTree a b) b that ‘trims’ the subtree depending on two
predicates p :: a -> Bool and q :: b -> Bool . In particular,
predicate p x returns True if and only if we should trim the leaf
storing some value x and q y returns True if and only if the
subtree whose root stores a y should be trimmed.
trimWhen :: (a -> Bool) -> (b -> Bool) -> LeafTree a b
-> LeafTree (Maybe (LeafTree a b)) b
trimWhen p q t = case t of
Leaf x | p x -> Leaf (Just t)
| otherwise -> Leaf Nothing
Node l y r | q y -> Leaf (Just t)
| otherwise -> Node (trimWhen p q l) y (trimWhen p q r)17 atHome
Write a function bimapTree :: (a -> c) -> (b -> d) -> LeafTree a b -> LeafTree c d.
bimapTree :: (a -> c) -> (b -> d) -> LeafTree a b -> LeafTree c d
bimapTree f g t = case t of
Leaf x -> Leaf (f x)
Node l x r -> Node (bimapTree f g l) (g x) (bimapTree f g r)18 atHome
Write a function trim :: Int -> LeafTree a b -> LeafTree (Maybe (LeafTree a b)
b) that trims a tree at the given depth.
trim :: Int -> LeafTree a b -> LeafTree (Maybe (LeafTree a b)) b
trim d = bimapTree f fst . trimWhen p p . withDepth
where
p :: (c,Int) -> Bool
p (_,d') = d' == d
f Nothing = Nothing
f (Just t) = Just $ bimapTree fst fst t19 atHome
Define a Tree type TTTree a that models trees in which
- the leaves store values of type
a, - internal nodes either have 2 or 3 children, and
- internal nodes store an ‘Int’ denoting the size (number of leaves) in the subtree.
data TTTree a = Leaf a
| Node2 Int (TTTree a) (TTTree a)
| Node3 Int (TTTree a) (TTTree a) (TTTree a)20 atHome
Define a function insert that inserts a new element in a TTTree,
while maintaining the subtree size invariant, and while keeping the
height low (e.g. try to avoid increasing the height if possible).
21 atHome
Define mapTTTree and foldTTTree functions for your TTTree data
type.
foldTTTree :: (a -> b) -> (Int -> b -> b -> b) -> (Int -> b -> b -> b -> b) -> TTTree a -> b
foldTTTree f g2 g3 t = case t of
Leaf x -> f x
Node2 s l r -> g2 s (foldTTTree f g2 g3 l) (foldTTTree f g2 g3 r)
Node3 s l m r -> g3 s (foldTTTree f g2 g3 l) (foldTTTree f g2 g3 m) (foldTTTree f g2 g3 r)
mapTTTree f = foldTTTree (Leaf . f) Node2 Node322 atHome
Define function sized that, given an Int \(n\), returns all subtrees
of size \(n\).
23 atHome
It is not possible to write the sized function directly using
foldTTTree. However, we can use foldTTTree to do most of the work;
that is, we can define a function sized' using foldTTTree such
that
sized :: Int -> TTTree a -> [TTTree a]
sized n = snd . sized' nwrite the function sized'
sized :: Int -> TTTree a -> (TTTRee a, [TTTree a])
sized n = foldTTTree f g2 g3
where
singleton s t = if n == s then [t] else []
f x = let t = Leaf x
in (t,singleton s t)
g2 s (l,ls) (r,rs) = let t = Node2 s l r
in (t, singleton s t ++ ls ++ rs)
g3 s (l,ls) (m,ms) (r,rs) = let t = Node3 s l m r
in (t, singleton s t ++ ls ++ ms ++ rs)24 atHome
A TTTree is valid if all root to leaf paths are equally
long. Write a function height that computes the height of a TTtree
if it is valid. Think about a suitable type for your function.
height :: TTTree a -> Maybe Int
height = foldTTTree (\_ -> Just 0)
(\_ lh rh -> inc $ lh <.> rh)
(\_ lh mh rh -> inc $ lh <.> mh <.> rh)
where
inc Nothing = Nothing
inc (Just h) = Just (h+1)
Nothing <.> _ = Nothing
Just h <.> Nothing = Nothing
Just h <.> Just hr | h == hr = Just h
| otherwise = Nothing25 Red-Black Trees atHome
Write a function validRBTree :: RBTree a -> Bool that checks if a
given RBTree a satisfies all red-black tree properties.
26 atHome
Consider the following data type of binary trees BST a that we
intend to use to implement binary search trees. We will store “real”
elements (the elements we care about) only in the Leaves of the
tree. The a field in a Node is used only as a routing element (to
guide searches).
data BST a = Leaf a
| Node (BST a) a (BST a)
deriving (Show,Read,Eq)We can compute the elements we care about of such a tree as follows:
elems :: BST a -> [a]
elems (Leaf x) = [x]
elems (Node l _ r) = elems l ++ elems rAn example of such a trees we will care about is
exampleTree = Node (Node (Leaf 1) 3 (Node (Leaf 4) 6 (Leaf 7))) 8 (Node (Leaf 9) 10 (Leaf 13))Then elems exampleTree = [1, 4, 7, 9, 13]
Here, the only purpose of the element 8, for example, is to signal that all the elements in the left subtree are \(\leq 8\) and that all the elements in the right subtree are \(> 8\).
The question: write a function complete that constructs a complete
balanced binary search tree out of an sorted list of \(2^h\), with \(h
\geq 0\), elements (with those elements in the same order as given.).
-- | This runs in O(n\log n) time.
complete :: [a] -> BST a
complete [x] = Leaf x
complete xs = let (ls,rs) = splitAt (n `div` 2) xs
n = length xs
in Node (complete ls) (last ls) (complete rs)Bonus: Write complete so that it runs in linear time.
27 atHome
Give the type of a function delete, such that, given an element a
and tree t, delete a t looks whether a is present in t and if
so, removes a from t. The function delete should always be able to
produce a valid element of the result type, i.e. it may not produce an
error.
delete :: Ord a => a -> BST a -> Maybe (BST a)28 atHome
Please implement the above function delete.
delete x t = case t of
Leaf y | x == y -> Nothing
| otherwise -> Just t
Node l k r | x <= k -> Just $ case delete x l of
Nothing -> r
Just l' -> Node l' k r
| otherwise -> Just $ case delete x r of
Nothing -> l
Just r' -> Node l k r'29 atHome
Use higher order functions (i.e. foldr, foldl', map, filter)
to write a function batchDelete that removes all elements from a
given list from a tree. Give the type of this function as well.
batchDelete :: Ord a => [a] -> BST a -> Maybe (BST a)
batchDelete xs t = foldr (\x mt -> mt >>= \t -> delete x t) (Just t) xs
where
-- This funny operator is called "bind" and is actually defined in
-- the prelude. It is the part of the Monad instance/definition of
-- the 'Maybe' type.
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x