## 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]`