2 Nov

# Higher order functions

Functions that take other functions as arguments

## Map

`map transform list`

applies `transform`

to each element of `list`

`transform`

is a function that takes *one* argument and returns its transformation

```
double x = x + x
> map double [1, 2, 3] -- apply the function to each element in the list
[2, 4, 6]
```

This way, `squares`

defined in Lab 2 can be rewritten as:

```
square x = x^2
> squares l = map square l
> squares [1, 2, 3, 4]
[1, 4, 9, 16]
```

## Filter

`filter predicate list`

keeps only elements of `list`

for which `predicate`

returns `True`

`predicate`

is a function that takes *one* argument and returns `True`

/`False`

```
isDivisible x = x `mod` 3 == 0
> filter isDivisible [1, 2, 3, 4, 5, 6] -- only keep elements where the function returns True
[3, 6]
```

This way, `squareEvens`

defined in Lab 2 can be rewritten as:

```
> squareEvens l = map square (filter even l)
> squareEvens [1, 2, 3, 4]
[4, 16]
```

## Fold

`fold aggregate start list`

repeatedly applies `aggregate`

to elements of `list`

, using `start`

as the initial value

`aggregate`

is a function that takes *two* arguments and returns their combination

`start`

is a *single* element, of the same type as those in `list`

```
customAdd x y = x + y + 10
> foldl customAdd 100 [1, 2, 3] -- aggeregate elements with the given function starting with the initial value
136 -- 100(initial) + 1(first element) +10(from customAdd) + 2 +10 + 3 +10
```

### foldl vs foldr

Commutative:

```
> foldl (+) [1, 2, 3] 0 -- starting from the left
6 -- 0 + 1 ~> (0+1) + 2 ~> ((0+1)+2) + 3 ~> 6
> foldr (+) [1, 2, 3] 0 -- starting from the right
6 -- 3 + 0 ~> 2 + (3+0) ~> 1 + (2+(3+0)) ~> 6
```

Non-commutative:

```
> foldl (++) "ABC" ["xy", "zt"] -- left
"ABCxyzt" -- ABC ~> ABC + xy ~> ABCxy + zt ~> ABCxyzt
> foldr (++) "ABC" ["xy", "zt"] -- right
"xyztABC" -- ABC ~> zt + ABC ~> xy + ztABC ~> xyztABC
```

# Function composition

```
triple x = x * 3
add5 x = x + 5
```

The following definitions are equivalent:

```
compound x = triple(add5 (x))
compound x = (triple . add5) x
compound x = triple . add5 $ x -- different way, less parentheses
compound = triple . add -- ommit the argument all-together
> compound 10
45 -- add5 (becomes 15) then triple (becomes 45)
```

This way, the above can be shortened as:

```
squares = map square
squareEvens = map square . filter even
```

## Arrow

`a >>> b`

passes the result of `a`

as an argument for `b`

Reverse order compared to `.`

– reads more like natural language

Defined in Lab 3, can also be imported from `Control.Arrow`

```
import Control.Arrow
compound = add5 >>> triple -- first add 5, then triple it
squareEvens = filter even >>> map square -- first keep even numbers then square them
```

# Lambdas and short-hands

A lambda is an anonymous function, the following are all equivalent:

```
> map double [1, 2, 3]
> map (\x -> x * 2) [1, 2, 3] -- because \ kind-of looks like a little lambda
> map (*2) [1, 2, 3] -- currying (more in later labs)
[1, 4, 9] -- all three yield the same thing
```

This way, the above can be shortened as:

```
square = (^2)
squares = map (^2)
squareEvens = map (^2) . filter even
```

# Pairs

A pair looks like `(a, b)`

```
> fst (1, 2) -- access first element
1
> snd (1, 2) -- access second element
2
```

`uncurry`

transforms a function that takes *two arguments* into one that takes *a pair*

```
> customAdd 2 3
15 -- 2 + 3 + 10
> pairwise = uncurry customAdd
> pairwise (2, 3)
15
> uncurry (-) 10 7 -- also works for operators
3
```

`zip`

creates pairs of elements from given lists:

```
> :t zip
zip :: [a] -> [b] -> [(a, b)]
> [1, 2, 3] `zip` [0, 0, 7]
[(1,0), (2,0), (3,7)]
> zip "abc" [0..] -- with an infinite list
[('a',0), ('b',1), ('c',2)]
```