200 lines
5.2 KiB
Text
200 lines
5.2 KiB
Text
Chapter 1: Functional Programming
|
|
===
|
|
|
|
> import Prelude hiding (foldl, foldr)
|
|
> import Control.Exception
|
|
|
|
Exercise 1.2
|
|
---
|
|
|
|
Trawling through Data.List we discovered the function
|
|
|
|
> uncons :: [a] -> Maybe (a, [a])
|
|
|
|
of whose existence we were quite unconscious. Guess the definition of uncons.
|
|
|
|
> uncons [] = Nothing
|
|
> uncons (hd : tl) = Just (hd, tl)
|
|
|
|
Exercise 1.3
|
|
---
|
|
|
|
The library Data.List does not provide functions
|
|
|
|
> wrap :: a -> [a]
|
|
> unwrap :: [a] -> a
|
|
> single :: [a] -> Bool
|
|
|
|
for wrapping a value into a singleton list, unwrapping a singleton list into
|
|
its sole occupant, and testing a list for being a singleton. This is a pity,
|
|
for the three functions can be very useful on occasions and will appear a
|
|
number of times in the rest of this book. Give appropriate definitions.
|
|
|
|
> -- return should work here too
|
|
> wrap x = [x]
|
|
>
|
|
> -- TBH unwrap should be returning Maybe since otherwise this throws an
|
|
> -- exception on unmatched cases
|
|
> unwrap [x] = x
|
|
>
|
|
> single [x] = True
|
|
> single _ = False
|
|
|
|
Exercise 1.4
|
|
---
|
|
|
|
Write down a definition of reverse that takes linear time. One possibility is to use a foldl.
|
|
|
|
> -- This takes linear time because the list basically builds up backwards
|
|
> reverse :: [a] -> [a]
|
|
> reverse = foldl (\a x -> x : a) []
|
|
|
|
Exercise 1.5
|
|
---
|
|
|
|
Express both map and filter as an instance of foldr.
|
|
|
|
> map2 :: (a -> b) -> [a] -> [b]
|
|
> map2 f = foldr (\x a -> f x : a) []
|
|
>
|
|
> filter2 :: (a -> Bool) -> [a] -> [a]
|
|
> filter2 f = foldr (\x a -> if f x then x : a else a) []
|
|
|
|
Exercise 1.6
|
|
---
|
|
|
|
Express `foldr f e . filter p` as an instance of foldr.
|
|
|
|
> composed :: (a -> b -> b) -> (a -> Bool) -> b -> [a] -> b
|
|
> composed f p e = foldr f e . filter p
|
|
>
|
|
> composed2 :: (a -> b -> b) -> (a -> Bool) -> b -> [a] -> b
|
|
> composed2 f p = foldr (\x a -> if p x then f x a else a)
|
|
|
|
Exercise 1.7
|
|
---
|
|
|
|
The function takeWhile returns the longest initial segment of a list all of
|
|
whose elements satisfy a given test. Moreover, its running time is proportional
|
|
to the length of the result, not to the length of the input. Express takeWhile
|
|
as an instance of foldr, thereby demonstrating once again that a foldr need not
|
|
process the whole of its argument before terminating.
|
|
|
|
> -- I think the fact that foldr doesn't consume the whole thing here is only
|
|
> -- due to laziness, since foldr builds up the expression from the back.
|
|
> takeWhile :: (a -> Bool) -> [a] -> [a]
|
|
> takeWhile f = foldr (\x a -> if f x then x : a else []) []
|
|
|
|
Exercise 1.8
|
|
---
|
|
|
|
The Data.List library contains a function dropWhileEnd which drops the longest
|
|
suffix of a list all of whose elements satisfy a given boolean test. For
|
|
example,
|
|
|
|
> _ = dropWhileEnd even [1, 4, 3, 6, 2, 4] == [1, 4, 3]
|
|
|
|
Define dropWhileEnd as an instance of foldr.
|
|
|
|
> dropWhileEnd :: Eq a => (a -> Bool) -> [a] -> [a]
|
|
> dropWhileEnd f = foldr (\x a -> if f x && a == [] then [] else x : a) []
|
|
|
|
Exercise 1.9
|
|
---
|
|
|
|
An alternative definition of foldr is
|
|
|
|
> foldr f e xs = if null xs then e else f (head xs) (foldr f e (tail xs))
|
|
|
|
Dually, an alternative definition of foldl is
|
|
|
|
> foldl f e xs = if null xs then e else f (foldl f e (init xs)) (last xs)
|
|
|
|
where last and init are dual to head and tail. What is the problem with this
|
|
definition of foldl?
|
|
|
|
> -- init and last are both O(n) operations since they require traversing to
|
|
> -- the end as opposed to head and tail which are O(1) which means overall this
|
|
> -- alternate definition of foldl is really expensive.
|
|
|
|
Exercise 1.10
|
|
---
|
|
|
|
Bearing the examples
|
|
|
|
> -- foldr (⊕) e [x, y, z] == x ⊕ (y ⊕ (z ⊕ e))
|
|
> -- foldl (⊕) e [x, y, z] == ((e ⊕ x) ⊕ y) ⊕ z
|
|
|
|
in mind, under what simple conditions on (⊕) and e do we have
|
|
|
|
> -- foldr (⊕) e xs = foldl (⊕) e xs
|
|
|
|
for all finite lists xs?
|
|
|
|
> -- (⊕) just needs to be associative and e the identity.
|
|
>
|
|
> -- This will give us x ⊕ (y ⊕ (z)) for foldr and (x ⊕ y) ⊕ z for foldl, which
|
|
> -- still preserves the order of x, y, and z so if (⊕) is associative then
|
|
> -- the statements are equivalent.
|
|
|
|
Exercise 1.11
|
|
---
|
|
|
|
Given a list of digits representing a natural number, construct a function
|
|
integer which converts the digits into that number. For example,
|
|
|
|
> _ = integer [1, 4, 8, 4, 9, 3] == 148493
|
|
|
|
Next, given a list of digits representing a real number r in the range 0 <= r <
|
|
1, construct a function fraction which converts the digits into the
|
|
corresponding fraction. For example,
|
|
|
|
> _ = fraction [1, 4, 8, 4, 9, 3] == 0.148493
|
|
|
|
> integer :: [Int] -> Int
|
|
> integer = foldl (\a x -> 10 * a + x) 0
|
|
>
|
|
> fraction :: [Int] -> Double
|
|
> fraction = (/ 10) . foldr (\x a -> fromIntegral x + a / 10) 0
|
|
|
|
Exercise 1.12
|
|
---
|
|
|
|
Complete the right hand sides of:
|
|
|
|
> -- map (foldl f e) . inits = ???
|
|
> -- map (foldr f e) . tails = ???
|
|
|
|
> -- TODO
|
|
|
|
Exercise 1.13
|
|
---
|
|
|
|
Define the function
|
|
|
|
> apply :: Int -> (a -> a) -> a -> a
|
|
|
|
that applies a function a specified number of times to a value.
|
|
|
|
> apply 0 f x = x
|
|
> apply n f x = apply (n - 1) f (f x)
|
|
|
|
Exercise 1.14
|
|
---
|
|
|
|
Can the function inserts associated with the inductive definition of perms be
|
|
expressed as an instance of foldr?
|
|
|
|
> -- TODO
|
|
|
|
Exercise 1.15
|
|
---
|
|
|
|
Give a definition of remove for which
|
|
|
|
> -- perms3 [] = [[]]
|
|
> -- perms3 xs = [x : ys | x <- xs, y <- perms3 (remove x xs)]
|
|
|
|
computes the permutations of a list. Is the first clause necessary? What is the
|
|
type of perms3, and can one generate the permutations of a list of functions
|
|
with this definition?
|