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

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