Declarative Programming

Answers to workshop exercises set 8.

QUESTION 1
Define versions of map for the following data types:

>data Ltree a = LTLeaf a | LTBranch (Ltree a) (Ltree a)
>data Cord a = Nil | Leaf a | Branch (Cord a) (Cord a)
>data Mtree a = Mnode a [Mtree a]

ANSWER

>ltree_map :: (a -> b) -> Ltree a -> Ltree b
>ltree_map f (LTLeaf a) = LTLeaf (f a)
>ltree_map f (LTBranch l r) = LTBranch (ltree_map f l) (ltree_map f r)

>cord_map :: (a -> b) -> Cord a -> Cord b
>cord_map f Nil = Nil
>cord_map f (Leaf a) = Leaf (f a)
>cord_map f (Branch l r) = Branch (cord_map f l) (cord_map f r)

For Mtrees we can use map (for lists) to process the list of subtrees.

>mtree_map :: (a -> b) -> Mtree a -> Mtree b
>mtree_map f (Mnode a mts) = Mnode (f a) (map (mtree_map f) mts)

QUESTION 2
In "foldr f b" we essentially replace [] by b and : by f. For example,

	foldr f (+) 0 [1, 2]
	= foldr f (+) 0 (1:2:[])
	= foldr f (+) 0 ((:) 1 ((:) 2 []))
	= ((+) 1 ((+) 2 0))
	= 1 + (2 + 0)
	= 3.

Similarly, foldr_tree f b (from the previous workshop) replaces Empty by b
and Node by f (which takes three arguments). Define versions of foldr
for the types in the previous question.

ANSWER
In all these foldr versions, we have to make some decision on the order
of the arguments for the different data constructors. Here we use the
reverse of the order they are given above, so base cases are last, like
foldr for lists and foldr_tree. Note the code is similar to the versions
of map, but we use these extra arguments in place of data constructors
on the right sides of equations.

>ltree_foldr :: (b -> b -> b) -> (a -> b) -> Ltree a -> b
>ltree_foldr _fb fl (LTLeaf a) = fl a
>ltree_foldr fb fl (LTBranch l r) =
>	fb (ltree_foldr fb fl l) (ltree_foldr fb fl r)

>cord_foldr :: (b -> b -> b) -> (a -> b) -> b -> Cord a -> b
>cord_foldr _fb _fl n Nil = n
>cord_foldr _fb fl _n (Leaf a) = fl a
>cord_foldr fb fl n (Branch l r) =
>	fb (cord_foldr fb fl n l) (cord_foldr fb fl n r)

For Mtrees we need arguments for Mnode, : and []. We can use foldr and
map (for lists) to process the list of subtrees:
	foldr fc n (map (mtree_foldr fn fc n) mts)
but the map and fold can be combined:

>mtree_foldr :: (a -> c -> b) -> (b -> c -> c) -> c -> Mtree a -> b
>mtree_foldr fn fc n (Mnode a mts) =
>	fn a (foldr (fc.(mtree_foldr fn fc n)) n mts)

Note the most general type has three type variables: (1) the type of the
original tree elements, (2) the final result type, and (3) the type that
a list of subtrees is converted into.

Some examples for testing:

>lt1 = LTBranch (LTLeaf 2) (LTLeaf 3)
>c1 = Branch (Leaf 2) (Branch (Leaf 3) Nil)
>mt1 = Mnode 2 [Mnode 3 []]

>ltree_sum = ltree_foldr (+) id
>cord_sum = cord_foldr (+) id 0
>mtree_sum = mtree_foldr (+) (+) 0

QUESTION 3
Recall the following functions from lectures, for concatenating a
list of lists and converting a cord into a list:

>concatr = foldr (++) []  -- Efficient
>concatl = foldl (++) []  -- Inefficient

>cord_to_list :: Cord a -> [a]  -- Inefficient
>cord_to_list Nil = []
>cord_to_list (Leaf x) = [x]
>cord_to_list (Branch a b) =
>    (cord_to_list a) ++ (cord_to_list b)

>cord_to_list2 :: Cord a -> [a]  -- Efficient
>cord_to_list2 c = cord_to_list' c []
>cord_to_list' :: Cord a -> [a] -> [a] -- Arg 2 is an accumulator
>cord_to_list' Nil rest = rest
>cord_to_list' (Leaf x) rest = x:rest
>cord_to_list' (Branch a b) rest =
>    cord_to_list' a (cord_to_list' b rest)

Recall the reason for the relative (in)efficiency is that ((a++b)++c)
has to copy the elements and cons cells of the list `a' twice, whereas
(a++(b++c)) only needs to do it once. The cost of ++ depends on the length
of its first argument but not its second argument.

Define four versions of concat_rev, which concatenates the lists in reverse
order (the inner lists are not reversed, for example concat_rev
[[1,2],[3]] = [3,1,2]) using (1) foldr, (2) foldl, (3) recursion without an
accumulator, and (4) recursion with an accumulator. Determine which versions
are efficient.

How would you code cord_to_list_rev, which converts a cord to a list,
but in the reverse order? Code it directly rather than creating an in-order
list and then reversing it.

What is the relationship between foldr for cords and the code above and
in what way is the code similar to both foldl and foldr?

ANSWER
For the fold versions we use the higher order flip function which
swaps the order of the arguments to (in this case) ++. This also swaps
the relative efficiency: while the time taken by ++ depends on the length
of its first argument, the time taken by  flip (++) depends on the length
of its second argument (since this becomes ++'s first argument).

>concat_rev1 = foldr (flip (++)) []  -- Inefficient
>concat_rev2 = foldl (flip (++)) []  -- Efficient

Foldl for lists is like using an accumulator; the following is efficient:

>concat_rev3 xss = concat_rev3_acc xss []

>concat_rev3_acc [] acc = acc
>concat_rev3_acc (xs:xss) acc = concat_rev3_acc xss (xs++acc)

Simple recursion without an accumulator is like foldr for lists; the
following is inefficient:

>concat_rev4 [] = []
>concat_rev4 (xs:xss) = (concat_rev4 xss) ++ xs

Because cords are a tree structure, the foldr version will still do lots
on inefficient concatenation (at least in the worst case). To get an
efficient version we must use an accumulator but traverse the tree in a
different order to that above. In fact, we need to traverse the tree
from left to right (the above version traverses it from right to left).
All we need to do is exchange a and b in the recursive calls in the last
line of the definition.

>cord_to_list_rev :: Cord a -> [a]  -- Efficient
>cord_to_list_rev c = cord_to_list_acc c []

>cord_to_list_acc :: Cord a -> [a] -> [a]
>cord_to_list_acc Nil rest = rest
>cord_to_list_acc (Leaf x) rest = x:rest
>cord_to_list_acc (Branch a b) rest =
>    cord_to_list_acc b (cord_to_list_acc a rest)

The simple (inefficient) definition of cord_to_list is essentially
the same as

cord_to_list = cord_foldr (++) (:[]) []

The efficient cord_to_list2 is like foldl in its use of an accumulator
but also like foldr in that it traverses from right to left.

QUESTION 4
The definition of the cord data type presented in lectures (see Q1 above)
can represent the same nonempty sequence of items in more than one way.
For example, the sequence [1, 2, 3] can be represented as
        Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
or as
        Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3)
Without this flexibility, the operation to concatenate two cords couldn't
be implemented in constant time. However, this type also has unnecessary
flexibility. For example, it can represent the empty sequence in more than
one way, including Nil, Branch Nil Nil and Branch Nil (Branch Nil Nil).
Design a version of the cord data type that has only way to represent
the empty sequence.

ANSWER
One possible design is

>data Cord' a
>        = EmptyCord
>        | NonEmptyCord (CordNode a)

>data CordNode a
>        = Leaf' a
>        | Branch' (CordNode a) (CordNode a)