Thinking Functionally with Haskell (28 page)

sortp x (y:us) vs

The claim is that if
as
is any permutation of
bs
then
sort as
and
sort bs
return the same result. The claim is intuitively obvious: sorting a list depends only on the elements in the input not on their order. A formal proof is omitted.

Carrying out a similar calculation in the case that
x <= y
and making
sortp
local to the definition of
sort
, we arrive at the final program

sort []
= []

sort (x:xs) = sortp xs [] []

where

sortp [] us vs
= sort us ++ [x] ++ sort vs

sortp (y:xs) us vs = if y < x

then sortp xs (y:us) vs

else sortp xs us (y:vs)

Not quite as pretty as before, but at least the result has Θ(
n
) space complexity.

Exercise A

One simple definition of
sort
is

This method is called
insertion sort
. Reduce
sort [3,4,2,1]
to head normal
form under lazy evaluation. Now answer the following questions: (i) How long, as a function of
n
, does it take to compute
head . sort
when applied to a list of length
n
? (ii) How long does it take under eager evaluation? (iii) Does insertion sort, evaluated lazily, carry out exactly the same sequence of comparisons as the following
selection sort
algorithm?

Exercise B

Write down a definition of
length
that evaluates in constant space. Write a second definition of
length
that evaluates in constant space but does not make use of the primitive
seq
(either directly or indirectly).

Exercise C

Construct
f
,
e
and
xs
so that
foldl f e xs
≠
foldl' f e xs

Exercise D

Would

be an alternative way of defining the function
cp
that is as efficient as the definition in terms of
foldr
? Yes, No or Maybe?

Time for a calculation. Use the fusion law of
foldr
to calculate an efficient alternative to
fcp = filter nondec . cp

See
Section 4.7
for a definition of
nondec
.

Exercise E

Suppose

T
(1) = Θ(1),

T
(
n
) =
T
(
n
div 2) +
T
(
n
−
n
div 2) +Θ(
n
) for 2 ≤
n
. Prove that
T
(2
^k
) = Θ(
k
2
^k
). Hence prove
T
(
n
) = Θ(
n
log
n
).

Exercise F

Prove that

Exercise G

Prove that if
h x (y,z) = (f x y,g x z)
, then

(foldr f a xs,foldr g b xs) = foldr h (a,b) xs

for all finite lists
xs
. A tricky question: does the result hold for
all
lists
xs
?

Now find a definition of
h
such that

(foldl f a xs,foldl g b xs) = foldl h (a,b) xs

Exercise H

Recall that

partition p xs = (filter p xs, filter (not . p) xs)

Express the two components of the result as instances of
foldr
. Hence use the result of the previous exercise to calculate another definition of
partition
.

Define

Calculate another definition of
partition
that uses
part
as a local definition.

Exercise I

Recall that

Compute
T
(
labels
)(
n
), where
n
is the number of leaves in the tree. Now use the accumulating parameter technique to find a faster way of computing
labels
. Prove that
labels (build xs) = xs
for all finite nonempty lists
xs
.

Exercise J

Define
select k = (!!k) . sort
, where
sort
is the original Quicksort. Thus
select k
selects the
k
th smallest element of a nonempty finite list of elements, the 0th smallest being the smallest element, the 1st smallest being the next smallest element, and so on. Calculate a more efficient definition of
select
and estimate its running time.

Answer to Exercise A

It takes Θ(
n
) steps to compute
head . sort
on a list of length
n
. Under eager evaluation it takes about
n
₂
steps. As to part (iii), the answer is yes. You may think we have defined sorting by insertion, but under lazy evaluation it turns out to be selection sort. The lesson here is that, under lazy evaluation, you don’t always get what you think you are getting.

Answer to Exercise B

For the first part, the following does the job:

length = foldl' (\n x -> n+1) 0

For the second part, one solution is

The test
n==0
forces evaluation of the first argument.

Answer to Exercise C

Take
f n x = if x==0 then undefined else 0
. Then

Answer to Exercise D

The answer is: maybe! Although the given version of
cp
is efficient, it returns the component lists in a different order than any of the definitions in the text. That probably doesn’t matter if we are only interested in the
set
of results, but it might affect the running time and result of any program that searched
cp
to find some list satisfying a given property.

According to the fusion rule we have to find a function
g
so that
filter nondec (f xs yss) = g xs (filter nondec yss)

where
f xs yss = [x:ys | x <- xs, ys <- yss]
. Then we would have

filter nondec . cp

= filter nondec . foldr f [[]]

= foldr g [[]]

Now

nondec (x:ys) = null ys || (x <= head ys && nondec ys)

That leads to

g xs [[]] = [[x] | x <- xs]

g xs yss
= [x:ys | x <- xs, ys <- yss, x <= head ys]

Answer to Exercise E

For the first part, we have

T
(2
^k
) = 2
T
(2
^k
−1
) +Θ(2
^k
).

By induction we can show
The induction step is

Hence
T
(2
^k
) = Θ(
k
2
^k
). Now suppose 2
^k
≤
n
< 2
^k
+1
, so Θ(
k
2
^k
) =
T
(2
^k
) ≤
T
(
n
) ≤
T
(2
^k
+1
) = Θ((
k
+1)2
^k
+1
) = Θ(
k
2
^k
).

Hence
T
(
n
) = Θ(
k
2
^k
) = Θ(
n
log
n
).

Answer to Exercise F

Define
x <> n = n+1
and
n @ x = 1+n
. We have
(x <> n) @ y = 1+(n+1) = (1+n)+1 = x <> (n @ y)

The second proof is similar.

Answer to Exercise G

The induction step is

The answer to the tricky question is No. The values (⊥, ⊥) and ⊥ are different in Haskell. For example, suppose we define
foo (x,y) = 1
. Then
foo undefined = undefined foo (undefined,undefined) = 1

For the last part, the definition of
h
is that

h (y,z) x = (f y x,g z x)

Answer to Exercise H

We have
filter p = foldr (op p) []
, where

op p x xs = if p x then x:xs else xs

Now

Hence

For the last part we obtain

Answer to Exercise I

Remember that
T
estimates the
worst case
running time. The worst case for
labels
arises when every right subtree of the tree is a leaf. Then we have
T
(
labels
)(
n
) =
T
(
labels
)(
n
−1) +Θ(
n
), where Θ(
n
) accounts for the time to concatenate a list of length
n
−1 with a list of length 1. Hence