{{% section %}}
Higher Order Functions
@wusyong, 吳昱緯
Higher order functions has at least one of...
- takes one or more functions as arguments
- returns a function as its result
Higher order functions are indispensable if we want to define computations by defining what stuff is instead of defining steps that change some state and maybe looping them
{{% /section %}}
{{% section %}}
Curried functions
- Every function in Haskell officially only takes one parameter.
- All the functions that accepted several parameters so far have been curried functions.
ghci> max 4 5
5
ghci> (max 4) 5
5
Function Application
max :: (Ord a) => a -> a -> a==max :: (Ord a) => a -> (a -> a)- max takes an a and returns a function that takes an a and returns an a
Partially Applied Function
Partial application (calling functions with too few parameters) is a neat way to create functions on the fly.
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z
ghci> let multTwoWithNine = multThree 9
ghci> multTwoWithNine 2 3
54
ghci> let multWithEighteen = multTwoWithNine 2
ghci> multWithEighteen 10
180
Partially Applied Function
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x
While compare has type of (Ord a) => a -> (a -> Ordering)
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100
Infix functions work too
To section an infix function, simply surround it with parentheses and only supply a parameter on one side.
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)
isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])
(-4) means minus 4 for convenience. Use (subtract 4) for infix section instead.
Without let to bind the name
ghci> multThree 3 4
<interactive>:1:0:
No instance for (Show (t -> t))
arising from a use of `print' at <interactive>:1:0-12
Possible fix: add an instance declaration for (Show (t -> t))
In the expression: print it
In a 'do' expression: print it
{{% /section %}}
{{% section %}}
Some higher-orderism is in order
Functions can take functions as parameters and also return functions.
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
Parentheses is now madatory here since they indicate first parameter is a function.
applyTwice
ghci> applyTwice (+3) 10
16
ghci> applyTwice (++ " HAHA") "HEY"
"HEY HAHA HAHA"
ghci> applyTwice ("HAHA " ++) "HEY"
"HAHA HAHA HEY"
ghci> applyTwice (multThree 2 2) 9
144
ghci> applyTwice (3:) [1]
[3,3,1]
zipWith
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]
[6,8,7,9]
ghci> zipWith' max [6,3,2,1] [7,3,1,5]
[7,3,2,5]
ghci> zipWith' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"]
["foo fighters","bar hoppers","baz aldrin"]
ghci> zipWith' (*) (replicate 5 2) [1..]
[2,4,6,8,10]
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]
[[3,4,6],[9,20,30],[10,12,12]]
flip
flip' :: (a -> b -> c) -> (b -> a -> c)
flip' f = g
where g x y = f y x
But -> is right associative by default.
flip' :: (a -> b -> c) -> b -> a -> c
flip' f y x = f x y
ghci> flip' zip [1,2,3,4,5] "hello"
[('h',1),('e',2),('l',3),('l',4),('o',5)]
ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]
[5,4,3,2,1]
{{% /section %}}
{{% section %}}
Maps and filters
map
map takes a function and a list and applies that function to every element in the list, producing a new list.
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
ghci> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
ghci> map (++ "!") ["BIFF", "BANG", "POW"]
["BIFF!","BANG!","POW!"]
ghci> map (replicate 3) [3..6]
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]
ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]
[[1,4],[9,16,25,36],[49,64]]
ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]
[1,3,6,2,2]
filter
filter is a function that takes a predicate and a list and then returns the list of elements that satisfy the predicate.
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
ghci> filter (==3) [1,2,3,4,5]
[3]
ghci> filter even [1..10]
[2,4,6,8,10]
ghci> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]
[[1,2,3],[3,4,5],[2,2]]
ghci> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"
"uagameasadifeent"
ghci> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"
"GAYBALLS"
Quick sort with filter
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort (filter (<=x) xs)
biggerSorted = quicksort (filter (>x) xs)
in smallerSorted ++ [x] ++ biggerSorted
largestDivisible
largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
where p x = x `mod` 3829 == 0
takeWhile
takeWhile takes a predicate and a list and then goes from the beginning of the list and returns its elements while the predicate holds true. Becasue of Haskell's property of laziness, list won't actually map and filter it right away. takeWhile forces the filtering and mapping to occur.
ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
166650
Collatz sequences
chain :: (Integral a) => a -> [a]
chain 1 = [1]
chain n
| even n = n:chain (n `div` 2)
| odd n = n:chain (n*3 + 1)
ghci> chain 10
[10,5,16,8,4,2,1]
ghci> chain 1
[1]
ghci> chain 30
[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Collatz sequences
numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
where isLong xs = length xs > 15
Let's used in partially applied functions
ghci> let listOfFuns = map (*) [0..]
ghci> (listOfFuns !! 4) 5
20
{{% /section %}}
{{% section %}}
Lambdas
Lambdas are basically anonymous functions that are used because we need some functions only once.
Lambdas: \
numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))
ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]
[153.0,61.5,31.0,15.75,6.6]
ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
[3,8,9,8,7]
Lamda as parameters
These two are the same
addThree :: (Num a) => a -> a -> a -> a
addThree x y z = x + y + z
addThree :: (Num a) => a -> a -> a -> a
addThree = \x -> \y -> \z -> x + y + z
Sometimes it is more readable
flip' :: (a -> b -> c) -> b -> a -> c
flip' f = \x y -> f y x
{{% /section %}}
{{% section %}}
Only folds and horses
A fold takes a binary function, a starting value (I like to call it the accumulator) and a list to fold up.
left fold: foldl
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs
ghci> sum' [3,5,2,1]
11
Or make it curried
sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
left fold: foldl
elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
right fold: foldr
Parameters order is reversed.
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs
foldl1 & foldr1
The first (or last) element of the list to be the starting value.
maximum' :: (Ord a) => [a] -> a
maximum' = foldr1 (\x acc -> if x > acc then x else acc)
product' :: (Num a) => [a] -> a
product' = foldr1 (*)
head' :: [a] -> a
head' = foldr1 (\x _ -> x)
last' :: [a] -> a
last' = foldl1 (\_ x -> x)
scanl & scanr
Report all the intermediate accumulator states in the form of a list.
ghci> scanl (+) 0 [3,5,2,1]
[0,3,8,10,11]
ghci> scanr (+) 0 [3,5,2,1]
[11,8,3,1,0]
ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]
[3,4,5,5,7,9,9,9]
ghci> scanl (flip (:)) [] [3,2,1]
[[],[3],[2,3],[1,2,3]]
scanl & scanr
Report all the intermediate accumulator states in the form of a list.
sqrtSums :: Int
sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1
ghci> sqrtSums
131
ghci> sum (map sqrt [1..131])
1005.0942035344083
ghci> sum (map sqrt [1..130])
993.6486803921487
{{% /section %}}
{{% section %}}
Function application with $
- $ is called function application but with lowest precedence.
- Usually f a b c is the same as ((f a) b) c) because it's left-associative.
- It becomes right-associative with $
($) :: (a -> b) -> a -> b
f $ x = f x
$ functions
- So
sum (map sqrt [1..130])==sum $ map sqrt [1..130] sum $ map sqrt [1..130]==sqrt $ 3 + 4 + 9sum (filter (> 10) (map (*2) [2..10]))==sum $ filter (> 10) $ map (*2) [2..10]- Since $ is function application, it can be treat as another function:
ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]
{{% /section %}}
{{% section %}}
Function composition
- Haskell does function composition with the . function:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
Make function on the fly to pass to other function
ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]
-- into
ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]
ghci> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]
[-14,-15,-27]
-- into
ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]
[-14,-15,-27]
Work well with $
sum (replicate 5 (max 6.7 8.9))
sum . replicate 5 . max 6.7) 8.9
sum . replicate 5 . max 6.7 $ 8.9
replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8])))
replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8]
Define pointless style function
sum' :: (Num a) => [a] -> a
sum' xs = foldl (+) 0 xs
sum' = foldl (+) 0
fn x = ceiling (negate (tan (cos (max 50 x))))
fn = ceiling . negate . tan . cos . max 50
Putting things together
oddSquareSum :: Integer
oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..]))
oddSquareSum :: Integer
oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]
oddSquareSum :: Integer
oddSquareSum =
let oddSquares = filter odd $ map (^2) [1..]
belowLimit = takeWhile (<10000) oddSquares
in sum belowLimit