# 08.09.07

## Exercise 9.12

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) |

solutions from the exercises in the book

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) |

map f (map g xs) = map (f.g) xs map (\x -> (x+1)/2) xs = map (/2) (map (+1) xs) |

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.

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 |

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.

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(n^{2}) 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.)

applyAll :: [(a -> a)] -> a -> a applyAll [] x = x applyAll (f:fs) x = f (applyAll fs x) |

applyEach :: [(a -> b)] -> a -> [b] applyEach [] _ = [] applyEach (f:fs) x = f x : applyEach fs x |