## Archive for August, 2007

### Exercise 9.12

Thursday, August 9th, 2007

Instances where we can curry and convert anonymous functions to sections are easy to find, for example from Exercise 5.5:

 doubleEach'' :: [Int] -> [Int] doubleEach'' = map (*2)

### Exercise 9.11

Thursday, August 9th, 2007
 map f (map g xs) = map (f.g) xs   map (\x -> (x+1)/2) xs = map (/2) (map (+1) xs)

### Exercise 9.10

Thursday, August 9th, 2007
 map ((/2).(+1)) xs

### Exercise 9.9

Wednesday, August 8th, 2007
 fix f = f (fix f)

First, f takes the result of fix f, and second, the return type of f must be the same as the return type of fix.

 fix :: (a -> a) -> a

Research shows that fix is the Fixed point combinator (or Y-combinator). Apparently this allows the definition of anonymous recursive functions. So let’s try to make remainder into an anonymous function. A good way to start is to simply remove one of the arguments and see if we can return an anonymous function. Something tells me that a is the argument to remove, since b is used in the base case.

 remanon b = (\f x -> if x < b then x else f (x-b))

That’s a good start. Note here that if we try to do something like:

 (remanon 3) remanon

Haskell says “unification would give infinite type” – which is a good sign. This is what we would like to do with the help of fix. So now if we apply fix to this, we get:

 fix (remanon b) = (remanon b) (fix (remanon b)) = (\x -> if x < b then x else (fix (remanon b)) (x-b))

Which looks good. So we need to fix remanon and apply it to a.

 remainder' a b = fix (remanon b) a

And that works.

### Exercise 9.8

Wednesday, August 8th, 2007
 power :: (a -> a) -> Int -> a -> a power f 0 = (\x -> x) power f n = (\x -> f (power f (n-1) x))

Since the function is called power, there is one obvious application that springs to mind, i.e. raising to a power:

 raise :: Int -> Int -> Int raise x y = power (*x) y 1

### Exercise 9.7

Wednesday, August 8th, 2007
 twice :: (a -> a) -> a -> a twice f = (\x -> f (f x))

twice twice applies the function 4 times:

 twice twice f = twice (\y -> f (f y)) = (\x -> (\y -> f (f y)) ((\y -> f (f y)) x)) = (\x -> (\y -> f (f y)) (f (f x))) = (\x -> f (f (f (f x))))

twice twice twice and twice (twice twice) each apply the function 16 times.

### Exercise 9.6

Wednesday, August 8th, 2007
 appendr = foldr (flip (++)) [] appendr [x,y,z] = foldr (flip (++)) [] [x,y,z] = flip (++) x (flip (++) y (flip (++) z [])) = flip (++) x (flip (++) y ([] ++ z)) = flip (++) x (([] ++ z) ++ y) = (([] ++ z) ++ y) ++ x

Running time of appendr is O(n2) since (++) traverses the length of its first argument.

 appendl = foldl (flip (++)) [] appendl [x,y,z] = foldl (flip (++)) [] [x,y,z] = flip (++) (flip (++) (flip (++) [] x) y) z = flip (++) (flip (++) (x ++ []) y) z = flip (++) (y ++ (x ++ [])) z = z ++ (y ++ (x ++ []))

Running time of appendl is O(n).

(Technical error 16 applies to this exercise.)

### Exercise 9.5

Wednesday, August 8th, 2007
 applyAll :: [(a -> a)] -> a -> a applyAll [] x = x applyAll (f:fs) x = f (applyAll fs x)

### Exercise 9.4

Wednesday, August 8th, 2007
 applyEach :: [(a -> b)] -> a -> [b] applyEach [] _ = [] applyEach (f:fs) x = f x : applyEach fs x

### Exercise 9.3

Wednesday, August 8th, 2007
 ys :: [Float -> Float]