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:

-- evens []        ==> []
-- evens [1,2,3,4] ==> [2,4]

evens       :: [Int] -> [Int]
evens []     = ... 
evens (x:xs) = ...

Example: four-letter words

Let’s write a function fourChars:

-- fourChars [] ==> []
-- fourChars ["i","must","do","work"] ==> ["must","work"]

fourChars :: [String] -> [String]
fourChars []     = ... 
fourChars (x:xs) = ...

Yikes, Most Code is the Same

Lets rename the functions to foo:

foo []            = []
foo (x:xs)
  | x mod 2 == 0  = x : foo xs
  | otherwise     =     foo xs

foo []            = []
foo (x:xs)
  | length x == 4 = x : foo xs
  | otherwise     =     foo xs

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

General Pattern

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

Specific Operations

• Predicates isEven and isFour

Avoid duplicating code!

Let’s talk about types

-- evens [1,2,3,4] ==> [2,4]
evens :: [Int] -> [Int]
evens xs = filter isEven xs
  where
    isEven :: Int -> Bool
    isEven x  =  x `mod` 2 == 0

filter :: ???

-- fourChars ["i","must","do","work"] ==> ["must","work"]
fourChars :: [String] -> [String]
fourChars xs = filter isFour xs
  where
    isFour :: String -> Bool
    isFour x  =  length x == 4

filter :: ???

So what’s the type of filter?

filter :: (Int -> Bool) -> [Int] -> [Int] -- ???

filter :: (String -> Bool) -> [String] -> [String] -- ???

• 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

-- For any type `a`
--   if you give me a predicate on `a`s
--   and a list of `a`s,
--   I'll give you back a list of `a`s 
filter :: (a -> Bool) -> [a] -> [a]

Example: all caps

Lets write a function shout:

-- shout []                    ==> []
-- shout ['h','e','l','l','o'] ==> ['H','E','L','L','O'] 

shout :: [Char] -> [Char]
shout []     = ...
shout (x:xs) = ... 

Example: squares

Lets write a function squares:

-- squares []        ==> []
-- squares [1,2,3,4] ==> [1,4,9,16] 

squares :: [Int] -> [Int]
squares []     = ...
squares (x:xs) = ...

Yikes, Most Code is the Same

Lets rename the functions to foo:

-- shout
foo []     = []
foo (x:xs) = toUpper x : foo xs

-- squares
foo []     = []
foo (x:xs) = (x * x)   : foo xs

Lets refactor into the common pattern

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

map f []     = []
map f (x:xs) = f x : map f xs

Lets refactor shout and squares

shout   = map ...

squares = map ...

QUIZ

What is the type of map?

map f []     = []
map f (x:xs) = f x : map f xs

(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]

-- For any types `a` and `b`
--   if you give me a transformation from `a` to `b`
--   and a list of `a`s,
--   I'll give you back a list of `b`s 
map :: (a -> b) -> [a] -> [b]

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?

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

quiz = map (\(x, y) -> x + y) [1, 2, 3]

(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

-- len []      ==> 0
-- len ["carne","asada"] ==> 2
len :: [a] -> Int
len []     = 0
len (x:xs) = 1 + len xs

Recall: summing a list

-- sum []      ==> 0
-- sum [1,2,3] ==> 6
sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs

Example: string concatenation

Let’s write a function cat:

-- cat [] ==> ""
-- cat ["carne","asada","torta"] ==> "carneasadatorta"
cat :: [String] -> String
cat []     = ...
cat (x:xs) = ...

Can you spot the pattern?

-- len
foo []     = 0
foo (x:xs) = 1 + foo xs

-- sum
foo []     = 0
foo (x:xs) = x + foo xs

-- cat
foo []     = ""
foo (x:xs) = x ++ foo xs

pattern = ...

The “fold-right” pattern

General Pattern

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

foldr f b []     = b
foldr f b (x:xs) = f x (foldr f b xs)

Let’s refactor sum, len and cat:

sum = foldr ...  ...

cat = foldr ...  ...

len = foldr ...  ...

Factor the recursion out!

You can write it more clearly as

sum = foldr (+) 0

cat = foldr (++) ""

The “fold-right” pattern

foldr f b [a1, a2, a3, a4]
  ==> f a1 (foldr f b [a2, a3, a4])
  ==> f a1 (f a2 (foldr f b [a3, a4]))
  ==> f a1 (f a2 (f a3 (foldr f b [a4])))
  ==> f a1 (f a2 (f a3 (f a4 (foldr f b []))))
  ==> f a1 (f a2 (f a3 (f a4 b)))

Accumulate the values from the right

For example:

foldr (+) 0 [1, 2, 3, 4]
  ==> 1 + (foldr (+) 0 [2, 3, 4])
  ==> 1 + (2 + (foldr (+) 0 [3, 4]))
  ==> 1 + (2 + (3 + (foldr (+) 0 [4])))
  ==> 1 + (2 + (3 + (4 + (foldr (+) 0 []))))
  ==> 1 + (2 + (3 + (4 + 0)))

QUIZ

What does this evaluate to?

foldr f b []     = b
foldr f b (x:xs) = f x (foldr f b xs)

quiz = foldr (\x v -> x : v) [] [1,2,3]

(A) Type error

(B) [1,2,3]

(C) [3,2,1]

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

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

foldr (:) [] [1,2,3]
  ==> (:) 1 (foldr (:) [] [2, 3])
  ==> (:) 1 ((:) 2 (foldr (:) [] [3]))
  ==> (:) 1 ((:) 2 ((:) 3 (foldr (:) [] [])))
  ==> (:) 1 ((:) 2 ((:) 3 []))
  ==  1 : (2 : (3 : []))
  ==  [1,2,3]

QUIZ

What is the most general type of foldr?

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f b []     = b
foldr f b (x:xs) = f x (foldr f b xs)

(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

Tail Recursion

Recursive call is the top-most sub-expression in the function body

• i.e. no computations allowed on recursively returned value

• i.e. value returned by the recursive call == value returned by function

QUIZ: Is this function tail recursive?

fac :: Int -> Int
fac n
  | n <= 1    = 1
  | otherwise = n * fac (n - 1)

fac 10000 ==> 10000 * (fac 9999) ==> 10000 * 9999 * (fac 9998)

facTR 10000 ==> loop 1 10000 ==> loop 10000 (9999) ==> loop (10000 * 9999) (9998) ==> loop (10000 * 9999 * 9998) (9997)

A. Yes

B. No

Tail recursive factorial

Let’s write a tail-recursive factorial!

facTR :: Int -> Int
facTR n = loop 1 n 
  where 
    loop acc n 
      | 1 <= n    = loop (acc * n) (n - 1)
      | otherwise = acc

def fac(n):
  acc = 1
  while (1 <= n):
    acc = acc * n
    n   = n - 1  
  return acc 

Lets see how facTR is evaluated:

facTR 4
  ==> loop 1  4     -- call loop 1 4
  ==> loop 4  3     -- rec call loop 4 3 
  ==> loop 12 2     -- rec call loop 12 2
  ==> loop 24 1     -- rec call loop 24 1
  ==> 24            -- return result 24! 

Each recursive call directly returns the result

• without further computation

• no need to remember what to do next!

• no need to store the “empty” stack frames!

Why care about Tail Recursion?

Because the compiler can transform it into a fast loop

facTR n = loop 1 n
  where
    loop acc n
      | n <= 1    = acc
      | otherwise = loop (acc * n) (n - 1)

function facTR(n){ 
  var acc = 1;
  while (true) {
    if (n <= 1) { return acc ; }
    else        { acc = acc * n; n = n - 1; }
  }
}

• Tail recursive calls can be optimized as a loop

  • no stack frames needed!

• Part of the language specification of most functional languages

  • compiler guarantees to optimize tail calls

Tail Recursive Fold

foldr f b []     = b
foldr f b (x:xs) = f x (foldr f b xs)

Is foldr tail recursive?

What about tail-recursive versions?

Let’s write tail-recursive sum!

sumTR :: [Int] -> Int
sumTR = ...

Lets run sumTR to see how it works

sumTR [1,2,3]
  ==> helper 0 [1,2,3]
  ==> helper 1   [2,3]    -- 0 + 1 ==> 1
  ==> helper 3     [3]    -- 1 + 2 ==> 3
  ==> helper 6      []    -- 3 + 3 ==> 6 
  ==> 6

Note: helper directly returns the result of recursive call!

Let’s write tail-recursive cat!

catTR :: [String] -> String 
catTR = ...

Lets run catTR to see how it works

catTR                 ["carne", "asada", "torta"]

  ==> helper ""       ["carne", "asada", "torta"]

  ==> helper "carne"           ["asada", "torta"]

  ==> helper "carneasada"               ["torta"]

  ==> helper "carneasadatorta"                 []

  ==> "carneasadatorta"

Note: helper directly returns the result of recursive call!

Can you spot the pattern?

-- sumTR
foo xs                = helper 0 xs
  where
    helper acc []     = acc
    helper acc (x:xs) = helper (acc + x) xs


-- catTR
foo xs                = helper "" xs
  where
    helper acc []     = acc
    helper acc (x:xs) = helper (acc ++ x) xs

pattern = ...

The “fold-left” 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

foldl f b xs          = helper b xs
  where
    helper acc []     = acc
    helper acc (x:xs) = helper (f acc x) xs

Let’s refactor sumTR and catTR:

sumTR = foldl ...  ...

catTR = foldl ...  ...

Factor the tail-recursion out!

QUIZ

What does this evaluate to?

foldl f b xs          = helper b xs
  where
    helper acc []     = acc
    helper acc (x:xs) = helper (f acc x) xs

quiz = foldl (\xs x -> x : xs) [] [1,2,3]

(A) Type error

(B) [1,2,3]

(C) [3,2,1]

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

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

foldl f b (x1: x2: x3 : [])
  ==> helper b (x1: x2: x3 : [])
  ==> helper (f x1 b)  (x2: x3 : [])
  ==> helper (f x2 (f x1 b))  (x3 : [])
  ==> helper (f x3 (f x2 (f x1 b)))  []
  ==> ( x3 :  (x2 : (x1 : [])))

The “fold-left” pattern

foldl f b                     [x1, x2, x3, x4]
  ==> helper b                [x1, x2, x3, x4]
  ==> helper (f b x1)             [x2, x3, x4]
  ==> helper (f (f b x1) x2)          [x3, x4]
  ==> helper (f (f (f b x1) x2) x3)       [x4]
  ==> helper (f (f (f (f b x1) x2) x3) x4)  []
  ==> (f (f (f (f b x1) x2) x3) x4)

Accumulate the values from the left

For example:

foldl (+) 0                   [1, 2, 3, 4]
  ==> helper 0                [1, 2, 3, 4]
  ==> helper (0 + 1)             [2, 3, 4]
  ==> helper ((0 + 1) + 2)          [3, 4]
  ==> helper (((0 + 1) + 2) + 3)       [4]
  ==> helper ((((0 + 1) + 2) + 3) + 4)  []
  ==> ((((0 + 1) + 2) + 3) + 4)

Left vs. Right

foldl f b [x1, x2, x3]  ==> f (f (f b x1) x2) x3  -- Left

foldr f b [x1, x2, x3]  ==> f x1 (f x2 (f x3 b))  -- Right

For example:

foldl (+) 0 [1, 2, 3]  ==> ((0 + 1) + 2) + 3  -- Left

foldr (+) 0 [1, 2, 3]  ==> 1 + (2 + (3 + 0))  -- Right

Different types!

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

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

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

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

Crucial foundation of

• “big data” revolution e.g. MapReduce, Spark, TensorFlow

• “web programming” revolution e.g. Jquery, Angular, React