Functional Programming
Sheet 7
29/11/03
> module Sheet7 where
Question 3
> data Liste a = Nil | Snoc (Liste a) a
> convert' :: Liste a -> [a] -> [a]
> convert' Nil = id
> convert' (Snoc xs x) = convert' xs . (x:)
> convert :: Liste a -> [a]
> convert xs = convert' xs []
Technique Acknowledgement:
http://www.haskell.org/hawiki/ListMutation
Question 4
(a)
> data Btree a = Tip a | Node (Btree a) (Btree a)
> subtrees :: Btree a -> [Btree a]
> subtrees (Tip n) = [Tip n]
> subtrees (Node left right) = (Node left right):(subtrees left ++ subtrees right)
> size :: Btree a -> Int
> size (Tip _) = 1
> size (Node left right) = size left + size right
In general, a tree of size n has (2n - 1) subtrees.
Proof:
First of all, here's an informal proof. A tree of size 1 has a single subtree (itself). To get from a tree of size n to
a tree of size (n+1), we replace a Tip with a Node with a Tip as each of its subtrees. This increases the number of
subtrees by 2 (since each of the two Tips is a subtree and there is still a subtree rooted at the Node). Thus there are
clearly (2n + c) subtrees of a tree of size n, for some c. Since a tree of size 1 has 1 subtree, c = -1, hence there are
(2n - 1) subtrees of a tree of size n.
We will now prove this formally by induction:
[Base Case]
length (subtrees (Tip n))
= length [Tip n] {defn. of subtrees}
= 1 {defn. of length}
= 2 * 1 - 1 {by arithmetic}
= 2 * (size (Tip n)) - 1 {defn. of size}
QED
[Inductive Hypothesis]
There exist subtrees of t - left, right - s.t.
length (subtrees left) = 2 * (size left) - 1 and length (subtrees right) = 2 * (size right) - 1 [hyp]
[Inductive Step]
Show that [hyp] => length (subtrees (Node left right)) = 2 * size (Node left right) - 1
length (subtrees (Node left right))
= length ((Node left right):(subtrees left ++ subtrees right)) {defn. of subtrees}
= 1 + length (subtrees left ++ subtrees right) {defn. of length}
= 1 + length (subtrees left) + length (subtrees right) {by the expected length and (++) relation}
= 1 + 2 * (size left) - 1 + 2 * (size right) - 1 {by [hyp]}
= 2 * (size left + size right) - 1 {by arithmetic}
= 2 * size (Node left right) - 1 {defn. of size}
QED
(b) (Additional Stuff)
i) A binary tree with values at the nodes as well as the leaves
> data BtreeB a = Leaf a | NodeB a (BtreeB a) (BtreeB a)
> mapBtreeB :: (a -> b) -> BtreeB a -> BtreeB b
> mapBtreeB f (Leaf n) = Leaf (f n)
> mapBtreeB f (NodeB n left right) = NodeB (f n) (mapBtreeB f left) (mapBtreeB f right)
> foldBtreeB :: (b -> b -> b -> b) -> (a -> b) -> BtreeB a -> b
> foldBtreeB _ g (Leaf n) = g n
> foldBtreeB f g (NodeB n left right) = f (foldBtreeB f g left) (g n) (foldBtreeB f g right)
ii) An expression tree evaluator - has some similarities to folding a tree
> data Etree a = Operand a | BinaryOp (a -> a -> a) (Etree a) (Etree a)
> evaluate :: Etree a -> a
> evaluate (Operand n) = n
> evaluate (BinaryOp f left right) = f (evaluate left) (evaluate right)
(c)
In the worst case, the running time of tips is O(n^2). Consider the perfectly unbalanced tree:
Node (Node (Node (Tip 1) (Tip 2)) (Tip 3)) (Tip 4)
Then we have:
tips (Node (Node (Node (Tip 1) (Tip 2)) (Tip 3)) (Tip 4))
= tips (Node (Node (Tip 1) (Tip 2)) (Tip 3)) ++ tips (Tip 4)
= tips (Node (Node (Tip 1) (Tip 2)) (Tip 3)) ++ [4]
= (tips (Node (Tip 1) (Tip 2)) ++ tips (Tip 3)) ++ [4]
= (tips (Node (Tip 1) (Tip 2)) ++ [3]) ++ [4]
= ((tips (Tip 1) ++ tips (Tip 2)) ++ [3]) ++ [4]
= (([1] ++ [2]) ++ [3]) ++ [4]
= ((1:([] ++ [2])) ++ [3]) ++ [4]
= (1:[2] ++ [3]) ++ [4]
= (1:([2] ++ [3])) ++ [4]
= (1:(2:([] ++ [3]))) ++ [4]
= 1:2:[3] ++ [4]
= 1:(2:[3] ++ [4])
= 1:(2:([3] ++ [4]))
= 1:(2:(3:([] ++ [4])))
= 1:2:3:[4]
= [1,2,3,4]
which is O(n^2).
(d)
> tipslist :: Btree a -> [a] -> [a]
> tipslist (Tip x) = (x:)
> tipslist (Node u v) = tipslist u . tipslist v
> tips :: Btree a -> [a]
> tips t = tipslist t []
The running time of this should now be O(n), since we'll just end up doing something like:
((1:) . (2:) . (3:) . (4:)) []
and (:) is a constant-time operation.
Question 6
It takes theta (phi ^ n) operations to evaluate fib n, where phi = (1 + sqrt 5) / 2. (See Bird P.235)