with Interpreters

and Functional Programming

Chapter 15

Higher Order Functions

**H. Conrad Cunningham**

**2 October 2018**

Copyright (C) 2017, 2018, H. Conrad Cunningham

**Acknowledgements**: I originally created these slides in Fall 2017 to accompany what is now Chapter 15, Higher Order Functions, in the 2018 version of the textbook *Exploring Languages with Interpreters and Functional Programming*.

**Browser Advisory**: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.

Demonstrate how to “think like a functional programmer”

Introduce concepts of first-class and higher-order functions

Illustrate how to generalize computational patterns

Develop useful library of higher-order list functions (

`map`

,`filter`

,`foldr`

,`foldl`

,`concatMap`

, etc)Reinforce correct, efficient, and elegant function designs

: (Ch. 2)*Procedural abstraction*- separates logical properties of computation from details of implementation

To perform

computation on*same*data structures*similar*encapsulate computation in

polymorphic function*first-order*pass data structure as argument

example:

`length :: [a] -> Int`

To perform

computations on*similar*data structures*similar*encapsulate computation in

polymorphic function*higher-order*also pass function for subcomputation as argument

example: same function can either add or multiply all elements of list

- First-class value:
can be stored in a data structure, passed as argument, returned as result

- Higher-order function (HOF):
takes functions as arguments or returns function as result

Haskell functions are first class values, can be higher-order

Haskell higher-order functions (HOF)

$\Longrightarrow$ construct powerful abstractions and operations

$\Longrightarrow$ express concise, “easy-to-understand” programs

$\Longrightarrow$ “glue together” programs from library functions and new program fragments

$\Longrightarrow$ improve programmer productivity and program reliability

`map`

)```
squareAll :: [Int] -> [Int]
squareAll [] = []
squareAll (x:xs) = (x * x) : squareAll xs
lengthAll :: [[a]] -> [Int]
lengthAll [] = []
lengthAll (xs:xss) = (length xs) : lengthAll xss
```

Take different kinds of data

Apply different operations

But both take list, apply function to each element, generate new list with same order and length

`map`

Generalizes

`squareAll`

,`lengthAll`

, and similar functionsAdds higher-order parameter

`f`

for operation appliedMakes input and output lists polymorphic of different types

`map`

```
squareAll2 :: [Int] -> [Int]
squareAll2 xs = map' sq xs
where sq x = x * x
lengthAll2 :: [[a]] -> [Int]
lengthAll2 xss = map' length xss
```

`sq`

and`length`

one-argument functionsWhat are

`map`

’s types`a`

and`b`

in above?

`map`

Under what circumstances does

`map' f xs`

terminate normally? (What preconditions?)What is time complexity of

`map f xs`

?What is space complexity of

`map f xs`

?

```
squareAll2 :: [Int] -> [Int]
squareAll2 xs = map' sq xs
where sq x = x * x
lengthAll2 :: [[a]] -> [Int]
lengthAll2 xss = map' length xss
```

What is time complexity of

`squareAll2 xs`

? space complexity?What is time complexity of

`lengthAll2 xs`

? space complexity?

`map`

is recursive list function, but can consider it:

powerful list operator

**transforming elements**simultaneouslyParallelism “easy” given referential transparency & immutable data—consider Google’s

`mapReduce`

operator node in dataflow network

Demand-driven network enabled by lazy evaluation stream $\longrightarrow$ [

`map`

node] $\longrightarrow$ transformed-stream

Do scope-commonality-variability analysis (SCV) on set of functions

scope: what is and is not included

commonalities: parts of functions that are same (frozen spots)

variabilities: parts of functions that differ (hot spots)

Leave commonalities in function body.

Move variabilities into type signature & parameter list

Move variabilities into type signature & parameter list

Make expression moved a function with parameter for each local variable accessed

Add type parameter to signature for types that differ among functions in scope

Add distinct type or value parameter for each potential role that type/value plays among functions in scope

Consider other approaches if many new parameters (e.g., new procedural or data abstractions)

`filter`

)Study similar functions

Take integer list and return integer list

For empty input, return empty output

Maintain relative order from input and output

Select some elements to copy; others not to copy

What is type of input and output list elements (

`Int`

type arbitrary)How to select value (

`getEven`

uses`even`

,`doublePos`

compares with 0)How to transform selected value (

`doublePos`

doubles,`getEven`

leaves unchanged)

`filter`

```
filter' :: (a -> Bool) -> [a] -> [a] -- filter in Prelude
filter' _ [] = []
filter' p (x:xs)
| p x = x : xs'
| otherwise = xs'
where xs' = filter' p xs
```

Takes and returns list of type

`[a]`

Takes predicate function

`p`

of type`a -> Bool`

Returns list containing elements that satisfy

`p`

in same orderBut does not implement transformation operation

`filter`

```
getEven2 :: [Int] -> [Int]
getEven2 xs = filter' even xs
doublePos2 :: [Int] -> [Int]
doublePos2 xs = map' dbl (filter' pos xs)
where dbl x = 2 * x
pos x = (0 < x)
```

Reuse

`map`

to transform data in`doublePos`

Restate three-leg definition of

`getEven`

/`doublePos`

in one legExcept simple local definitions in

`doublePos`

, which we eliminate later

`filter`

```
filter' :: (a -> Bool) -> [a] -> [a] -- filter in Prelude
filter' _ [] = []
filter' p (x:xs)
| p x = x : xs'
| otherwise = xs'
where xs' = filter' p xs
```

Under what circumstances does

`filter' p xs`

terminate normally? (What preconditions?)What is time complexity of

`filter' p xs`

?What is space complexity of

`filter' p xs`

?

```
getEven2 :: [Int] -> [Int]
getEven2 xs = filter' even xs
doublePos2 :: [Int] -> [Int]
doublePos2 xs = map' dbl (filter' pos xs)
where dbl x = 2 * x
pos x = (0 < x)
```

What is the time complexity of

`getEven2 xs`

? space complexity?What is the time complexity of

`doublePos2 xs`

? space complexity?

`foldr`

)Study similar functions

Take list

Insert binary operator between consecutive list elements (associative for these)

Reduce list to single return value

Group operations right to left

Return some value for nil list (as “rightmost” value of nonempty)

Here value is (right) identity of operation

Differ in element type (

`Int`

,`Integer`

,`[a]`

)Differ in operation inserted (addition, multiplication, list append)

Differ in value returned for nil input list—(right) identity element (0, 1,

`[]`

)Differ in return type (

`Int`

,`Integer`

,`a`

)Here each same as input element type, but can it differ?

Is associativity important? identity?

Do not assume

Observe operations of type

`a -> a -> a`

Consider more general operations of type

`a -> b -> b`

$\Longrightarrow$ return value of type

`b`

for empty or nonempty lists

`foldr`

(1)```
foldrX :: (a -> b -> b) -> b -> [a] -> b -- foldr in Prelude
foldrX f z [] = z
foldrX f z (x:xs) = f x (foldrX f z xs)
```

Separates input element type

`a`

from output value type`b`

Takes general binary operation

`f`

(of type`a -> b -> b`

) to “fold” listTakes “seed” value

`z`

(of type`b`

) as return for empty listsDoes not depend upon operation being associative or having identity

`foldr`

(2)```
foldrX :: (a -> b -> b) -> b -> [a] -> b -- foldr
foldrX f z [] = z
foldrX f z (x:xs) = f x (foldrX f z xs)
```

`foldr f z [1,2,3]`

expands to

`foldr`

`foldr`

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

Under what circumstances does

`foldrX f z xs`

terminate normally? (What preconditions?)What is time complexity of

`foldrX f z xs`

? space complexity?Backward recursive, so possible stack overflow for complex

`f`

or long`xs`

```
product2 :: [Int] -> Int -- product
product2 xs = foldrX (*) 1 xs
concat2:: [[a]] -> [a] -- concat
concat2 xss = foldrX (++) [] xss
```

What is time complexity of

`product2 xs`

? space complexity?What is time complexity of

`concat2 xs`

? space complexity?

`foldr`

for `map`

`map inc [1,2] = mf 1 (mf 2 [])`

where`inc x = x+1`

Moving right to left folding function

`mf`

applies map function

`f`

to next elementattaches result as head of processed tail

Uses nil list for seed—

`mf`

has no identity but`foldr`

useful!

`foldr`

for `filter`

```
filter2 :: (a -> Bool) -> [a] -> [a] -- filter
filter2 p xs = foldr ff [] xs
where ff y ys = if p y then (y:ys) else ys
```

`filter2 gt2 [1,3] = ff 1 (ff 3 [])`

where`gt2 x = x > 2`

Uses nil list for seed for filtered result

Moving right to left folding function

`ff`

applies filter predicate

`p`

to next elementif holds, attaches element as head of filtered result; else omits

`foldr`

for `length`

`length2 [1,2] = len 1 (len 2 0)`

Uses seed value 0 as initial value of counter

Moving right to left folding function

`len _ acc= acc + 1`

takes next element as left argument and counter as right

returns incremented counter

`foldr`

for `append`

`append2 [1,2] [3,4] = 1 : (2 : [3,4])`

Uses entire second argument of

`++`

as seed valueMoving right to left through left argument of

`++`

, folding function`(:)`

- attaches next element as head of resulting appended list

`foldr`

,`filter`

, and`map`

are backward recursive functionsBut think of them as powerful operators on whole lists

`foldl`

)```
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [1,2,3] == f 1 (f 2 (f 3 z))
== 1 `f` (2 `f` (3 `f` z))
```

What about same functionality except group from left?

`foldl`

```
foldlX :: (a -> b -> a) -> a -> [b] -> a -- foldl
foldlX f z [] = z
foldlX f z (x:xs) = foldlX f (f z x) xs
```

Inserts “seed” value as leftmost element

Uses “seed” value parameter as accumulator—tail recursive

Has different type signature

If $\oplus$ is an associative binary operation of type `t -> t -> t`

with identity element `z`

then, for any finite `xs`

.

`foldr (`

$\oplus$`) z xs = foldl (`

$\oplus$`) z xs`

`sum`

,`product`

, and`concat`

all satisfyWhich of

`foldr`

or`foldl`

better to use?

*Strict*function parameter means argument value always required by function evaluation*Nonstrict*function parameter means argument value sometimes not requiredAddition and multiplication strict in both parameters (operands)

`++`

strict in first parameter and nonstrict in second

If operation $\oplus$

*nonstrict*in either argument, then often better to use`foldr`

—exploits lazy evaluationIf operations $\oplus$

*strict*in both arguments, then more efficient to use`foldl'`

from library`Data.List`

`foldr`

or `foldl`

(1)Implement

`concat`

with`foldr`

because`++`

nonstrict in secondImplement

`sum`

and`product`

with`foldl'`

because`+`

an`*`

strict in both

`foldr`

or `foldl`

(2)Uses

`foldl`

Like

`length2`

except`len`

arguments reversed`length2`

better choice because`len`

nonstrict list argument

`foldr`

or `foldl`

(3)Similar to the tail recursive

`reverse`

`foldl`

’s`z`

parameter initially nil`foldl`

’s`f`

parameter uses`(:)`

to build list in reverse order`reverse2`

cannot exploit lazy evaluation on`(:)`

’s right argument because of its initializationBetter to use tail recursion

`foldl`

for `foldr`

```
foldr2 :: (a -> b -> b) -> b -> [a] -> b -- foldr
foldr2 f z xs = foldl flipf z (reverse xs)
where flipf y x = f x y
```

- Avoids possible stack overflow by reversing list, using tail recursive
`foldl`

`concatMap`

)`concatMap`

for `filter`

First-class and higher-order functions

Generalizing computational patterns as higher-order functions

Using library of list-transforming functions

Thinking like a functional programmer

The Haskell code module for this section is in file `HigherOrderFunctions.hs`