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