Thinking Functionally with Haskell by Richard Bird

Author:Richard Bird [Bird, Richard]
Language: eng
Format: epub, azw3, pdf
Publisher: Cambridge University Press
Published: 2014-10-31T00:00:00+00:00

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

foldl f 0 [0,2] = 0

foldl' f 0 [0,2] = undefined

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(2k) = 2T(2k−1) +Θ(2k).

By induction we can show The induction step is

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

Hence T(n) = Θ(k2k) = Θ(nlogn).

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

(foldr f a (x:xs),foldr g b (x:xs)

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

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

= h x (foldr h (a,b) xs

= foldr h (a,b) (x:xs)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.