Declarative Programming
Answers to workshop exercises set 7.
QUESTION 1
Foldr takes a list and "folds" it into a single value, but that
value could be any type, including a list. Can you implement map and
filter using foldr?
ANSWER
>map' f xs = foldr ((:).f) [] xs
>filter' p xs = foldr (\x->if p x then (x:) else id) [] xs
QUESTION 2
Consider the task of converting a list of single element lists into
a sorted list by repeatedly merging lists. This is a fold operation.
What is the algorithmic complexity if we use "foldr merge []"? What if
we use foldl instead of foldr? Is the result the same, and why or why not?
What is the complexity? What if we use balanced_fold (defined in lectures)?
ANSWER
Foldr and foldl both result in O(N^2) complexity. Essentially these are
variations on insertion sort - we repeatedly merge a single element list
with a sorted list, which is like inserting an element into a sorted list.
They produce the same result because merge is associative, with identity [].
With balanced_fold we get O(N log N) complexity (a version of merge sort).
QUESTION 3
There are two improvements we can make to the definition of the
balanced_fold function given in lectures.
The balanced_fold function given in lectures computes the length of not just
the original list, but of every one of the lists it is divided into,
even though the code that divides a list knows (or should know) how long
the resulting lists should be. The first improvement is therefore avoiding
the redundant length computations, and computing the length of just one list:
the original list.
The second improvement is to avoid the intermediate lists being created
at each level of recursion, when the list is split in two. An alternative
is for the first recursive call to return both the fold of the first
half (or n elements) of the list and the remainder of the list (which
is then used in the second recursive call). For example, using the scenario
from the previous question, doing a merge using balanced folds on the list
of lists [[4],[1],[6],[2],[8],[7],[3],[5]], the first recursive call could
return the pair ([1,2,4,6], [[8],[7],[3],[5]]), and then pass the list
of lists [[8],[7],[3],[5]] to the second call.
Write two versions of balanced_fold. The first should have the first of these
improvements, the second should have both.
You might want also want to code merge sort (for example) in this style,
and then generalise it to balanced_fold.
ANSWER
Here is the version with both improvements:
>balanced_fold' :: (e -> e -> e) -> e -> [e] -> e
>balanced_fold' f b xs = fst (bal_fold1 f b xs (length xs))
>
>bal_fold1 :: (e -> e -> e) -> e -> [e] -> Int -> (e, [e])
>bal_fold1 _ b xs 0 = (b, xs)
>bal_fold1 _ _ (x:xs) 1 = (x, xs)
>bal_fold1 f b xs len = -- len > 1
> let
> len1 = len `div` 2
> len2 = len - len1
> (value1, rest1) = bal_fold1 f b xs len1
> (value2, rest2) = bal_fold1 f b rest1 len2
> in
> (f value1 value2, rest2)
For completeness, here is a version of merge sort which uses this.
Here we use map (with an operator section) instead of a separate
"to_single_els" function.
>mergesort :: (Ord a) => [a] -> [a]
>mergesort xs = balanced_fold' merge [] (map (:[]) xs)
>merge [] ys = ys
>merge (x:xs) [] = x:xs
>merge (x:xs) (y:ys)
> | x <= y = x : merge xs (y:ys)
> | x > y = y : merge (x:xs) ys
QUESTION 4
Consider the following tree data type:
>data Tree a = Empty | Node (Tree a) a (Tree a)
Define a higher order function
>map_tree :: (a->a) -> Tree a -> Tree a
which is the analogue of map for trees (rather than lists): it applies
a function to each element of the tree and produces a new tree containing
the results. The result tree is the same shape as the input tree, just
as the result list in map is the same length as the input list.
ANSWER
>map_tree _ Empty = Empty
>map_tree f (Node l n r) = Node (map_tree f l) (f n) (map_tree f r)
QUESTION 5
Given the Tree type above, write functions which take a Tree and compute
(a) the height,
(b) the number of nodes,
(c) the concatenation of the elements in the nodes (assuming that the
values in tree nodes are in fact lists)
(d) the sum of the elements (assuming that values in the tree are Nums)
(e) the product of the elements in the nodes (assuming they are Nums), and
(f) Just the maximum of the elements in the nodes, or, Nothing if the tree
is empty Nothing.
Before you start, it may be helpful to review the tree sort question
from the workshop for week 4.
These operations can be seen as folds on Trees. When you get tired of writing
the same pattern for traversing the Tree, write a higher order function
>foldr_tree :: (a->b->a->a) -> a -> Tree b -> a
which can be used to define the other functions. The first argument is
a function which is applied at each Node, after the subtrees have been
folded. The second argument is returned for Empty trees.
ANSWER
I'm already tired of writing that pattern, so I'll go directly to the
higher order function :-)
>foldr_tree _ b Empty = b
>foldr_tree f b (Node l n r) = f (foldr_tree f b l) n (foldr_tree f b r)
Note that below we use "curried" functions - there is no reference to
the tree. Type inference does a pretty good job, though it s not perfect
because type classes are involved. For sum_tree and product_tree it infers
the elements are Integers (we should add a type declaration saying they
are Nums). For max_tree it fails to infer a type, so we have to add a
type declaration.
>height_tree = foldr_tree (node_max_plus_1) 0
> where node_max_plus_1 l _ r = 1 + max l r
>size_tree = foldr_tree node_plus_1 0
> where node_plus_1 l _ r = 1 + l + r
>sum_tree = foldr_tree (ternary (+)) 0
>product_tree = foldr_tree (ternary (*)) 1
>concat_tree = foldr_tree (ternary (++)) []
>max_tree :: Ord a => Tree a -> Maybe a
>max_tree = foldr_tree node_max Nothing
> where node_max l n r = maybe_max (maybe_max l (Just n)) r
Ternary takes a binary function and turns it into a ternary one by
applying it twice (this pattern occurs three times above, so it is worth
doing). Right associativity is used (so ++ is faster). The type could
actually be more general (x and y don't have to be the same type as z
and the return type).
>ternary :: (a -> a -> a) -> a -> a -> a -> a
>ternary f x y z = f x (f y z)
Max wrapped up in Maybe.
>maybe_max :: (Ord a) => Maybe a -> Maybe a -> Maybe a
>maybe_max Nothing Nothing = Nothing
>maybe_max (Just x) Nothing = (Just x)
>maybe_max Nothing (Just x) = (Just x)
>maybe_max (Just x) (Just y) = Just (max x y)
A couple of very simple test cases:
>t1 = Node Empty 3 (Node Empty 4 Empty)
>t2 = Node Empty [3] (Node Empty [4,5] Empty)