08.09.07

Exercise 9.12

Posted in Uncategorized at 9:13 pm by admin

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)

Permalink 1 Comment

Exercise 9.11

Posted in Uncategorized at 8:36 pm by admin

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

Permalink Comments

Exercise 9.10

Posted in Uncategorized at 8:34 pm by admin

map ((/2).(+1)) xs

Permalink Comments

08.08.07

Exercise 9.9

Posted in Uncategorized at 11:52 pm by admin

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.

Permalink 2 Comments

Exercise 9.8

Posted in Uncategorized at 11:18 pm by admin

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

Permalink 2 Comments

Exercise 9.7

Posted in Uncategorized at 11:13 pm by admin

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.

Permalink 1 Comment

Exercise 9.6

Posted in Uncategorized at 10:52 pm by admin

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

Permalink Comments

Exercise 9.5

Posted in Uncategorized at 10:35 pm by admin

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

Permalink 4 Comments

Exercise 9.4

Posted in Uncategorized at 10:34 pm by admin

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

Permalink 1 Comment

Exercise 9.3

Posted in Uncategorized at 10:33 pm by admin

ys :: [Float -> Float]

Permalink Comments