Higher-Order Functions

Plan for this week

Last week:

  • user-defined data types
    • and how to manipulate them using pattern matching and recursion
  • how to make recursive functions more efficient with tail recursion

This week:

  • code reuse with higher-order functions (HOFs)

  • some useful HOFs: map, filter, and fold










Recursion is good…

  • Recursive code mirrors recursive data

    • Base constructor -> Base case
    • Inductive constructor -> Inductive case (with recursive call)

  • But it can get kinda repetitive!










Example: evens

Let’s write a function evens:







Example: four-letter words

Let’s write a function fourChars:










Yikes, Most Code is the Same

Lets rename the functions to foo:

Only difference is condition

  • x mod 2 == 0 vs length x == 4










Moral of the day


D.R.Y. Don’t Repeat Yourself!


Can we

  • reuse the general pattern and
  • substitute in the custom condition?










HOFs to the rescue!

General Pattern

  • expressed as a higher-order function
  • takes customizable operations as arguments

Specific Operation

  • passed in as an argument to the HOF







The “filter” pattern

The filter Pattern
The filter Pattern

General Pattern

  • HOF filter
  • Recursively traverse list and pick out elements that satisfy a predicate

Specific Operations

  • Predicates isEven and isFour
filter instances
filter instances

Avoid duplicating code!










Let’s talk about types












So what’s the type of filter?


  • It does not care what the list elements are

    • as long as the predicate can handle them

  • It’s type is polymorphic (generic) in the type of list elements








Example: all caps

Lets write a function shout:







Example: squares

Lets write a function squares:










Yikes, Most Code is the Same

Lets rename the functions to foo:



Lets refactor into the common pattern







The “map” pattern

The map Pattern
The map Pattern

General Pattern

  • HOF map
  • Apply a transformation f to each element of a list

Specific Operations

  • Transformations toUpper and \x -> x * x





Lets refactor shout and squares





map instances
map instances










QUIZ

What is the type of map?

(A) (Char -> Char) -> [Char] -> [Char]

(B) (Int -> Int) -> [Int] -> [Int]

(C) (a -> a) -> [a] -> [a]

(D) (a -> b) -> [a] -> [b]

(E) (a -> b) -> [c] -> [d]











Type says it all!

  • The only meaningful thing a function of this type can do is apply its first argument to elements of the list

  • Hoogle it!


Things to try at home:

  • can you write a function map' :: (a -> b) -> [a] -> [b] whose behavior is different from map?

  • can you write a function map' :: (a -> b) -> [a] -> [b] such that map' f xs returns a list whose elements are not in map f xs?










QUIZ

What is the value of quiz?

(A) [2, 4, 6]

(B) [3, 5]

(C) Syntax Error

(D) Type Error

(E) None of the above











Don’t Repeat Yourself

Benefits of factoring code with HOFs:

  • Reuse iteration pattern

    • think in terms of standard patterns

    • less to write

    • easier to communicate

  • Avoid bugs due to repetition










Recall: length of a list






Recall: summing a list






Example: string concatenation

Let’s write a function cat:







Can you spot the pattern?











The “fold-right” pattern

The foldr Pattern
The foldr Pattern

General Pattern

  • Recurse on tail
  • Combine result with the head using some binary operation







Let’s refactor sum, len and cat:

Factor the recursion out!










foldr instances
foldr instances

You can write it more clearly as










QUIZ

What does this evaluate to?

(A) Type error

(B) [1,2,3]

(C) [3,2,1]

(D) [[3],[2],[1]]

(E) [[1],[2],[3]]



















The “fold-right” pattern

Accumulate the values from the right

For example:










QUIZ

What is the most general type of foldr?

(A) (a -> a -> a) -> a -> [a] -> a

(B) (a -> a -> b) -> a -> [a] -> b

(C) (a -> b -> a) -> b -> [a] -> b

(D) (a -> b -> b) -> b -> [a] -> b

(E) (b -> a -> b) -> b -> [a] -> b











Is foldr tail recursive?










What about tail-recursive versions?

Let’s write tail-recursive sum!










Lets run sumTR to see how it works

Note: helper directly returns the result of recursive call!










Let’s write tail-recursive cat!










Lets run catTR to see how it works

Note: helper directly returns the result of recursive call!










Can you spot the pattern?











The “fold-left” pattern

The foldl Pattern
The foldl Pattern

General Pattern

  • Use a helper function with an extra accumulator argument
  • To compute new accumulator, combine current accumulator with the head using some binary operation







Let’s refactor sumTR and catTR:

Factor the tail-recursion out!









QUIZ

What does this evaluate to?

(A) Type error

(B) [1,2,3] ———–

(C) [3,2,1] ———–

(D) [[3],[2],[1]]

(E) [[1],[2],[3]]










QUIZ

What does this evaluate to?


(A) Type error

(B) [1,2,3]

(C) [3,2,1]

(D) [[3],[2],[1]]

(E) [[1],[2],[3]]










The “fold-left” pattern

Accumulate the values from the left

For example:










Left vs. Right

For example:

Different types!










Useful HOF: flip

What is the type of flip?










Useful HOF: compose

What is the type of (.)?











Higher Order Functions

Iteration patterns over collections:

  • Filter values in a collection given a predicate
  • Map (iterate) a given transformation over a collection
  • Fold (reduce) a collection into a value, given a binary operation to combine results

Useful helper HOFs:

  • Flip the order of function’s (first two) arguments
  • Compose two functions


HOFs can be put into libraries to enable modularity

  • Data structure library implements map, filter, fold for its collections

    • generic efficient implementation

    • generic optimizations: map f (map g xs) --> map (f.g) xs

  • Data structure clients use HOFs with specific operations

    • no need to know the implementation of the collection

Enabled the “big data” revolution e.g. MapReduce, Spark












That’s all folks!