cse130

Bottling Computation Patterns

Another way to practice D.R.Y:

spot common computation patterns
refactor them into reusable higher-order functions (HOFs)
useful library HOFs: map, filter, and fold

Example: evens

Let’s write a function evens that extracts only even elements from an integer list.

-- 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 the 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

filter bottles the common pattern of selecting elements from a list that satisfy a condition:

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 bottles the common pattern of iteratively applying a transformation to each element of a list:

EXERCISE: refactor with map

With map defined as:

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

refactor shout and squares to use map:

shout   xs = map ...

squares xs = map ...

The Case of the Missing Parameter

The following definitions of shout are equivalent:

shout :: [Char] -> [Char]
shout xs = map (\x -> toUpper x) xs

and

shout :: [Char] -> [Char]
shout = map toUpper

Where did xs and x go???

The Case of the Missing Parameter

Recall lambda calculus:

The expressions F and \x -> F x are in some sense “equivalent”

as long as x not in FV(F)

because they behave the same way when applied to any argument E:

(\x -> F x) E
=b> F E

Transforming \x -> F x into F is called eta contraction

and the reverse is called eta expansion

In Haskell we have:

shout xs = map (\x -> toUpper x) xs

is syntactic sugar for:

shout
  =d>
\xs -> map (\x -> toUpper x) xs
  =e> -- eta-contract outer lambda
map (\x -> toUpper x)
  =e> -- eta-contract inner lambda
map toUpper

More generally, whenever you want to define a function:

f x y z = E x y z

you can save some typing, and omit the parameters:

as long as x, y, and z are not free in E

f = E

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]

The type of “map”

-- 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!

Can you think of a function that:

has this type
builds the output list not by applying the transformation to the input list?

Example: summing a list

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

Example: string concatenation

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

Can you spot the pattern?

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

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

pattern = ...

The “fold-right” pattern

foldr op base []     = base
foldr op base (x:xs) = op x (foldr op base xs)

General Pattern

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

foldr bottles the common pattern of combining/reducing a list into a single value:

EXERCISE: refactor with fold

With foldr defined as:

foldr op base []     = base
foldr op base (x:xs) = op x (foldr op base xs)

refactor sum and cat to use foldr:

sum xs = foldr op base xs
  where
    base     = ...
    op x acc = ...

cat xs = foldr op base xs
  where
    base     = ...
    op x acc = ...

Now use eta-contraction to make your code more concise!

Solution

sum xs = foldr op base xs
  where
    base     = 0
    op x acc = x + acc

cat xs = foldr op base xs
  where
    base     = ""
    op x acc = x ++ acc

or, more concisely:

sum = foldr (+) 0

cat = foldr (++) ""

Executing “foldr”

To develop some intuition about foldr lets “run” it by hand.

foldr op base []     = base
foldr op base (x:xs) = op x (foldr op base xs)

foldr op b (a1:a2:a3:[])
==>
  a1 `op` (foldr op b (a2:a3:[]))
==>
  a1 `op` (a2 `op` (foldr op b (a3:[])))
==>
  a1 `op` (a2 `op` (a3 `op` (foldr op b [])))
==>
  a1 `op` (a2 `op` (a3 `op` b))

Look how it mirrors the structure of lists!

(:) is replaced by op
[] is replaced by base

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)))

Accumulate the values from the right!

QUIZ

What is the most general type of foldr?

foldr op base []     = base
foldr op base (x:xs) = op x (foldr op base 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

QUIZ

Recall the function to compute the len of a list

len :: [a] -> Int
len []     = 0
len (x:xs) = 1 + len xs

Which of these is a valid implementation of len

A. len = foldr (\n -> n + 1) 0

B. len = foldr (\n m -> n + m) 0

C. len = foldr (\_ n -> n + 1) 0

D. len = foldr (\x xs -> 1 + len xs) 0

E. None of the above

HINT: remember that foldr :: (a -> b -> b) -> b -> [a] -> b!

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

process = ...

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

Also, since foldl already has the b argument, which can serve as accumulator, the helper is redundant! Can be rewritten as:

foldl op base []     = base
foldl op base (x:xs) = foldl op (base `op` x) xs

Let’s refactor sumTR and catTR:

sumTR = foldl ...  ...

catTR = foldl ...  ...

Factor the tail-recursion out!

The “fold-left” pattern

foldl op b                                  [x1, x2, x3, x4]
  ==> foldl op (b `op` x1)                      [x2, x3, x4]
  ==> foldl op ((b `op` x1) `op` x2)                [x3, x4]
  ==> foldl op (((b `op` x1) `op` x2) `op` x3)          [x4]
  ==> foldl op ((((b `op` x1) `op` x2) `op` x3) `op` x4)  []
  ==> (((b `op` x1) `op` x2) `op` x3) `op` x4

Accumulate the values from the left

For example:

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

Left vs. Right

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

foldr op b [x1, x2, x3]  ==> x1 `op` (x2 `op` (x3 `op` 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

EXERCISE: list reversal two ways

Write a function that reverses a list first using foldr and then using foldl.

reverser :: [a] -> [a]
reverser = foldr op base
  where
    base     = ...
    op x res = ...

and

reversel :: [a] -> [a]
reversel = foldl op base
  where
    base     = ...
    op acc x = ...

Which one is more efficient?

Recall:

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

-- Computation patterns:
foldl op b [x1, x2, x3]  ==> ((b `op` x1) `op` x2) `op` x3
foldr op b [x1, x2, x3]  ==> x1 `op` (x2 `op` (x3 `op` b))

Useful HOF: flip

-- you can write
foldl (\xs x -> x : xs) [] [1,2,3]

-- more concisely like so:
foldl (flip (:))        [] [1,2,3]

What is the type of flip?

flip :: ???

Useful HOF: compose

-- you can write
map (\x -> f (g x)) ys

-- more concisely like so:
map (f . g) ys

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

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!