A higher-order function, is a function which takes another as input. There are a number of useful ones that have been included in the prelude.

map :: (a->b) -> [a] -> [b]

Applies a function to each element of a list e.g.

map (*2) [1,2,3] = [2,4,6]

If you are having trouble, try to write the following functions.

  • A function to double all elements in a list
  • A function to add one to all elements in a list
filter :: (a -> Bool) -> [a] -> [a]

Applies a Boolean function to each element of a list and returns a list of elements that returned true. e.g.

filter (isEven) [1,2,3,4] = [2,4]

If you are having trouble, try to write the following functions. *A function to remove all odds from a list *A function to remove all instances of ‘a’

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Combines too lists together with a function.

If you are having trouble, try to write the following functions. *A function to tuple two lists together *Adds two lists element-wise

foldl :: (a -> b -> b) -> [a] -> b

Folds can be used to implement any function where you traverse a list once, element by element, and then return something based on that. Whenever you want to traverse a list to return something, chances are you want a fold. Fold left does this by applying the function to a recursive call.

If you’re having trouble, try to write ‘sum’

foldr :: (a -> b -> b) -> b -> [a] -> b

Fold right does this with an identity/accumulator and is tail recursive. e.g.

sum = foldr (+) 0

Read through these definitions and try to implement them using composition of higher order functions.

  1. product :: (Num a) => [a] -> a calcualtes the product of a list of numbers, remember to use fold!
  2. dotProduct :: (Num a) => [a] -> [a] -> a calculates the dot product of two vectors.
  3. oneMatch :: a -> [a] -> Bool returns true if at least one element from the input list matches the input target and false if no elements match. Hint what does the all and any functions do in haskell? They both have the type signature :(a -> Bool) -> [a] -> Bool
  4. treeZipWith :: (a -> b -> c) Tree a -> Tree b -> Tree c Takes a function and two trees and zips them up into a single new tree. Think about how regular zipWith is defined and apply that to treeZipWith.
  5. treeFold :: (a -> b -> b) -> Tree a -> b -> b aims to reduce every single node of a tree into a single value. Where Tree a = (Node a (Tree a) (Tree a)). Think about how you actually need to fold the tree up. Can you start at the top or do you need to start at the leaves?