Question: Writing List Recursion Functions

Here are some questions to help you revise list recursion. Note that the Answers are just one of many possible implementations.

  1. Implement the function addOne :: [Int] -> [Int] which takes a list and adds one to each element. E.g addOne [1, 2] = [2, 3].

Answer:

addOne :: [Int] -> [Int]
addOne [] = []
addOne (x:xs) = (x + 1) : (addOne xs)
  1. Implement the function multiplyN :: Int -> [Int] -> [Int] which takes a list and multiplies each element by a constant so multiplyN 3 [1, 2] = [3, 6].

Answer:

multiplyN :: Int -> [Int] -> [Int]
multiplyN n [] = []
multiplyN n (x:xs) = (x * n) : (multiplyN n xs)
  1. Implement the function addList :: (Num a) => [a] -> [a] -> [a] which takes two lists and adds each element to the corresponding element in the other list, so addList [3, 5] [1, 2] = [4, 7]. Note that addList should produce an error if the lists have different lengths.

Answer:

addList :: (Num a) => [a] -> [a] -> [a]
addList l1 l2 = case (l1, l2) of
    ([], [])     -> []
    (x:xs, y:ys) -> (x + y) : (addList xs ys)
    _            -> error "Lists do not have the same length"
  1. Implement the function removeNegative :: [Int] -> [Int] which takes a list and removes all the negative elements, so addList [1, -2, 3, -4] = [1, 3].

Answer:

removeNegative :: [Int] -> [Int]
removeNegative [] = []
removeNegative (x:xs)
    | x < 0 = removeNegative xs
    | otherwise = x : (removeNegative xs)

Questions: Type Signatures for Higher Order Functions

Below, we have a variety of function definitions. All of these define higher order functions. For each, add the type signature. Remember to use polymorphism to make them as general as possible!

apply :: ____________
apply f x = f x

Answer:

apply :: (a -> b) -> a -> b

curry :: ____________
curry f x y = f (x,y)

Answer:

curry :: ((a,b) -> c) -> a -> b -> c

multiplyTwice :: ____________
multiplyTwice n = (\x -> x * n * n)

Answer:

multiplyTwice :: (Num a) => a -> (a -> a)

Questions: Type Signatures to Function Definition

Now we have the opposite: a lot of type signatures but no function definitions! Fill in the blanks and define the functions below based on their names, inputs and type signatures:

add :: Int -> (Int -> Int)
add n = ____________

Answer:

add n = (\x -> x + n)

choose :: Int -> [a -> b] -> a -> b
choose i listOfFunctions x = ____________

Answer:

choose i listOfFunctions x = (listOfFunctions !! i) x

Questions: Your Own Higher Order Function

Write the type signature for and define a higher order function that does the following: takes in two functions and a tuple and then applies the first function to the left tuple value and the second function to the right tuple value. This will return a tuple. For example:

func (+1) toUpper (0, 'i') = (1, I)

Answer:

func :: (a -> b) -> (c -> d) -> (a,c) -> (b,d)
func f1 f2 (a,b) = (f1 a, f2 b)

Questions: Writing Higher Order Functions on Lists

Now that you have some familiarity with higher order functions which operate on lists, have a go at writing your own version of the functions! Do this for map, zipWith, foldl and foldr.

Answers:

map :: (a -> b) -> [a] -> [b]
map f ls = case ls of
    []     -> []
    (x:xs) -> f x : map f xs

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipwith f (x:xs) (y:ys) = (f x y) : (zipwith f xs ys)
zipwith _ _ _           = []
    
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z ls = case ls of
    []     -> z
    (x:xs) -> foldl f (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z ls = case ls of
    []     -> z
    (x:xs) -> f x (foldr f z xs)