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