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)
Exercise 9.11
map f (map g xs) = map (f.g) xs map (\x -> (x+1)/2) xs = map (/2) (map (+1) xs)
08.08.07
Exercise 9.9
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
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
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
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
applyAll :: [(a -> a)] -> a -> a applyAll [] x = x applyAll (f:fs) x = f (applyAll fs x)
Exercise 9.4
applyEach :: [(a -> b)] -> a -> [b] applyEach [] _ = [] applyEach (f:fs) x = f x : applyEach fs x