Lecture 17-1

COMP105 Lectures 2020-11-17

More Higher Order Functions

Scan

The scan set of functions is similar to the fold set of functions. However instead of outputting a single value it outputs a list showing the accumulator at each step in the function:

> scanr (+) 0 [1,2,3,4]
> [10,9,7,4,0]

The function scanr is implemented like so:

scanr' :: (a-> b -> b ->) -> b -> [a] -> [b]

scanr' _ init [] = [init]
scanr' f init (x:xs) =
	let
		recursed = scanr' f init xs
		new = f x (head recursed)
	in
		new : recursed

Scan Variants

There are also left to right versions of scan:

> scanl (+) 0 [1..10]
> [0,1,3,6,10,15,21,28,36,45,55]

A good way to understand the accumulator in a fold is to do a scan and observe the output.

Fibonacci Example

fib_pairs n = scanl (\ (a,b _ -> (b,a + b)) (0,1) [1..n]
fib_to_n n = map fst (fib_pairs n)

> fib_pairs 3
> [(0,1),(1,1),(1,2)]

> fib_to_n 3
> [0,1,1]

Exercises

```
 prefixMaximum list = scanl1 max list
```
As max is already a two argument function that takes acc and x, then we don’t have to make our own anonymous function.

 powersOfTwo n = scanl (\ acc _ -> 2 * acc) 1 [1..n]