Skip to content
Switch branches/tags
Go to file
Cannot retrieve contributors at this time

1. Exercises from chapter 9-10 of The Craft of Functional Programming

1a. Define the length function using map and sum

length xs = sum . map (\_ -> 1)

1b. What does map (+1) (map (+1) xs) do? Can you conclude anything in general about properties of map f (map g xs) where f and g are arbitrary functions?

The function map (+1) (map (+1) xs) creates an array that increments each element by 2. In general, map f (map g xs) is equal to map (f . g) xs

1c. Give the type of, and define the function iter so that iter n f x = f (f (... (f x))) where f occurs n times on the right-hand side of the equation. For instance, we should have iter 3 f x = f (f (f x)) and iter 0 f x should return x.

iter :: Int -> (a -> a) -> a -> a
iter 0 _ = id
iter n f = iter (n - 1) f . f

1d. What is the type and effect of the following function?

\n -> iter n succ

succ is the successor function, which increases a value by one:

The type of the function is Enum a => Int -> a -> a

1e. How would you define the sum of the squares of the natural numbers 1 to n using map and foldr?

squaresSum n = foldr (+) 0 squares 
    squares = map (^2) [1..n]

1f. How does the function behave?

mystery xs = foldr (++) [] (map sing xs)
    sing x = [x]

Maps each element of the list in to a single element list and then concatenate them. The output is equivalent to the original list.

1g. If id is the polymorphic identity function, defined by id x = x, explain the behavior of the expressions (id . f), (f . id), (id f). If f is of type Int -> Bool, at what instance of its most general type a -> a is id used in each case?

(id . f) x = (id :: Bool -> Bool) (f x) = f x
(f . id) x = f ((id :: Int -> Int) x) = f x
(id f) = (id :: (Int -> Bool) -> (Int -> Bool)) f = f

1h. Define a function composeList which composes a list of functions into a single function. You should give the type of composeList, and explain why the function has this type. What is the effect of your function on an empty list of functions?

Assumption: composeList [f, g, h] x = f (g (h x))

composelist :: [(a -> a)] -> a -> a
composeList = foldr (.) id

The elements of the list have to be of the type (a -> a) because even though a list consisting of [(c -> d), (b -> c), (a -> b)] can be composed to a -> d, the constraint cannot be easily expressed using the haskell type system.

Using the above definition of composeList then composeList [] = id, which is quite reasonable.

1i. Define the function flip::(a->b->c)->(b->a->c) which reverses the order in which its function argument takes its arguments. The following example shows the effect of flip: flip div 3 100 = 33

flip f a b = f b a

2. List Comprehensions and Higher-Order Functions

2a. Can you rewrite the following list comprehensions using the higher-order functions map and filter? You might need the function concat too.

  1. [x + 1 | x <- xs]
map (+1) xs
  1. [x+y|x<-xs,y<-ys]
concat (map (\x -> map (+x) ys) xs)
  1. [x+2|x<-xs,x>3]
map (+2) (filter (>3) xs) 
  1. [x+3|(x,_)<-xys]
map ((+3) . fst) xs
  1. [x+4|(x,y)<-xys,x+y<5]
map ((+4) . fst) $ filter (\(x,y) -> x + y < 5) xys
  1. [x + 5 | Just x <- mxs]
  isJust Nothing = False
  isJust (Just x) = True
  map ((+5) . \(Just x) -> x) (filter isJust mxs) 

2b. Can you it the other way around? I.e. rewrite the following expressions as list comprehensions.

  1. map (+3) xs
[x+3 | x <- xs]
  1. filter (>7) xs
[x | x <- xs , x > 7]
  1. concat (map (\x -> map (\y -> (x,y)) ys) xs)
[(x, y) | x <- xs, y <- ys]
  1. filter (>3) (map (\(x,y) -> x+y) xys)
[x+y | (x,y) <- xys, x+y > 3]

3. Generating Lists

A. Write a generator listOfLength :: Integer -> Gen a -> Gen [a] such that listOf n g generates a list of n elements, where each element is generated by g. What property would you write to test that your generator behaves as it should?

listOfLength :: Int -> Gen a -> Gen [a]
listOfLength n = sequence . take n . repeat

prop_ListOfLength :: Property
prop_ListOfLength = forAll (choose (4, 24)) $ \n -> 
  ((== n) . length) <$> (listOfLength n arbitrary :: Gen [Int])

B. Now use listOf to write a generator that generates pairs of lists of the same, random, length.

pairsOfSameLengthLists :: Gen Int -> Gen a -> Gen ([a],[a])
pairsOfSameLengthLists lenGen elemGen = do 
  length <- lenGen
  xs <- listOfLength length elemGen
  ys <- listOfLength length elemGen
  return (xs,ys)

prop_PairsOfSameLengthLists :: Property
prop_PairsOfSameLengthLists = 
  forAll (pairsOfSameLengthLists lenGen elemGen) hasSameLength
    hasSameLength (xs,ys) = length xs == length ys
    lenGen = choose (4,20)
    elemGen = arbitrary :: Gen Double

C.Take a look at the standard Haskell functions zip and unzip:

zip :: [a] -> [b] -> [(a,b)] 
unzip :: [(a,b)] -> ([a],[b])

Write down two properties for these; one that says that zip is the inverse of unzip, and one that unzip is the inverse of zip. Note that unzip is not always the inverse of zip, so you need a condition! Could you make use of the generator you just defined?

Hint: make a datatype

data TwoSameLengthLists a = SameLength [a] [a]

and use your generator for part B. to make a generator for the above type. Then, make the above type an instance of Arbitrary. Finally, you can use it to write your property.

instance Arbitrary a => Arbitrary (TwoSameLengthLists a) where
  arbitrary = do 
    (xs, ys) <- pairsOfSameLengthLists (choose (4, 20)) arbitrary
    return (SameLength xs ys)

prop_ZipInverseOfUnzip :: [(Int, Int)] -> Bool
prop_ZipInverseOfUnzip xys = 
    (xs, ys) = unzip xys
    zip xs ys == xys

prop_UnzipInverseOfZip :: TwoSameLengthLists Int -> Bool
prop_UnzipInverseOfZip (SameLength xs ys) =
  unzip (zip xs ys) == (xs,ys)