Higher-Order Functions
Thumrongsak Kosiyatrakul
Thumrongsak Kosiyatrakul
Higher-Order Functions
Higher-Order Function
Every function in Haskell takes exactly one argument Consider the function max
ghci> max 5 12
ghci> :t max
max :: Ord a => a -> a -> a
We usually think that the max function takes two arguments
All functions that look like they take more than one argument in Haskell are curried functions
For all functions that take more than one arguments:
they take exactly one argumentand
they return a function that take other argument(s) and so on
Higher-Order Functions
Thumrongsak Kosiyatrakul
Curried Functions
Let’s check the type of the function max 5: ghci> :t max 5
max 5 :: (Ord a, Num a) => a -> a
max 5 has type a -> a which is a function that takes one argument of type a and returns a value of type a
Since max 5 is a function, we can bind it to a variable and use it as a new function:
ghci> maxWith5 = max 5
ghci> :t maxWith5
maxWith5 :: (Ord a, Num a) => a -> a ghci> maxWith5 12
ghci> maxWith5 3
We can also think that the type of the function max is max :: Ord a => a -> (a -> a)
Takes one argument of type a and returns a function of type a -> a
Higher-Order Functions
Thumrongsak Kosiyatrakul
Partially Applied Functions
A partially applied function is a function that returned by a function that is called with too few arguments
ghci> :t min 32
min 32 :: (Ord a, Num a) => a -> a ghci> :t take 5
take 5 :: [a] -> [a]
This is a pretty neat way to create new functions on the fly Start with an existing function
Partially apply with argument(s) Get a new (more specific) function
Higher-Order Functions
Thumrongsak Kosiyatrakul
New More Specific Functions
Suppose we want to create a function that compare a number with 99:
ghci> compareWith99 x = compare 99 x
ghci> :t compareWith99
compareWith99 :: (Ord a, Num a) => a -> Ordering ghci> compareWith99 52
ghci> compareWith99 99 EQ
ghci> compareWith99 104 LT
From the above definition, we can also omit the variable x:
ghci> compareWith99 = compare 99
ghci> :t compareWith99
compareWith99 :: (Ord a, Num a) => a -> Ordering
Higher-Order Functions
Thumrongsak Kosiyatrakul
Suppose you want to create a function that returns a given number divided by 2:
ghci> div2 x = x / 2 ghci> div2 123
Note that we need to partially apply 2 as the second argument of the function /
We can section the function / by surround it with parentheses and supply a argument on one side:
ghci> div2 = (/2) ghci> div2 123 61.5
Here is a neat way to check whether a character is an uppercase letter:
ghci> isUpper = (`elem` [‘A’..’Z’]) ghci> isUpper ‘T’
ghci> isUpper ‘x’
Higher-Order Functions
Thumrongsak Kosiyatrakul
Print a Function???
What if we want to print a function:
ghci> max 5
ghci> isUpper
Functions are not instances of the Show type class NotethatwecanprintisUpper ’H’becauseitisevaluatedto
True which has type Bool (an instance of the Show type class)
Higher-Order Functions
Thumrongsak Kosiyatrakul
Higher-Order Function
In Functional programming, functions are the first class citizen Functions are treated as data
Functions can be arguments to other functions Return values can be functions
In Haskell, functions can take other functions as arguments Example:
ghci> applyTwice f x = f (f x) ghci> :t applyTwice
applyTwice :: (t -> t) -> t -> t ghci> :t succ
succ :: Enum a => a -> a
ghci> :t applyTwice succ
applyTwice succ :: Enum t => t -> t ghci> applyTwice succ 5
applyTwice takes a function of type t -> t as the first argument
Higher-Order Functions
Thumrongsak Kosiyatrakul
Higher-Order Function
Any functions of type t -> t will do More examples:
ghci> applyTwice (+10) 34 54
ghci> applyTwice (*2) 23 92
ghci> applyTwice (++ ” World”) “Hello” “Hello World World”
ghci> applyTwice (9 🙂 [1,2]
ghci> :t (9 🙂
(9 🙂 :: Num a => [a] -> [a]
Note that we use sections with +, *, ++, and : operators
Higher-Order Functions
Thumrongsak Kosiyatrakul
The zipWith Function Consider the zipWith Function
ghci> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith takes a function and two lists as arguments, and then joins the two lists by applying the function between corresponding elements
ghci> zipWith (+) [1,2,3] [3,7,5] [4,9,8]
ghci> zipWith (+) [1,2,3] [3,7] [4,9]
ghci> zipWith (+) [1,2] [3,7,5] [4,9]
ghci> zipWith max [2,4,1] [1,5,3] [2,5,3]
ghci> zipWith min [2,4,1] [1,5,3] [1,4,1]
Let’s define our own zipWith
Higher-Order Functions
Thumrongsak Kosiyatrakul
The myZipWith Function
Obviously, if a given list is empty, myZipWith should return the empty list
However, if given lists are x:xs and y:ys and the given function is f:
We need to apply the function f to x and y
The result becomes the first element of the resulting list
What about lists xs and ys?
Zip them with the same function and use the result as the rest of the resulting list
Here is our myZipWith:
myZipWith _ [] _ = []
myZipWith _ _ [] = []
myZipWith f (x:xs) (y:ys) = f x y : myZipWith f xs ys
Higher-Order Functions
Thumrongsak Kosiyatrakul
The myZipWith Function
Some tests:
ghci> myZipWith (++) [“Hello”, “Love”] [” World”, ” Haskell”] [“Hello World”,”Love Haskell”]
ghci> myZipWith (++) (myZipWith (++) [“Hello”, “Love”] [” “, ” “])
[“World”, “Haskell”]
[“Hello World”,”Love Haskell”]
ghci> myZipWith (*) (replicate 5 10) [1..]
[10,20,30,40,50]
ghci> myZipWith (myZipWith (*)) [[1,2],[3,4]] [[5,6],[7,8]] [[5,12],[21,32]]
myZipWith (*) is a function of type [c] -> [c] -> [c]
Higher-Order Functions
Thumrongsak Kosiyatrakul
The flip Function
Let’s practice with the function flip
ghci> :t flip
flip :: (a -> b -> c) -> b -> a -> c
The flip function takes a function and returns a function where arguments are flipped
Mathematically
flip(𝑓(𝑥,𝑦)) = 𝑓(𝑦,𝑥)
This can be easily implement in Haskell since functions are treated as data
myFlip :: (a -> b -> c) -> b -> a -> c
myFlip f x y = f y x
Higher-Order Functions
Thumrongsak Kosiyatrakul
The flip Function
Some tests:
ghci> zip [1,2,3] “Dog” [(1,’D’),(2,’o’),(3,’g’)]
ghci> myFlip zip [1,2,3] “Dog” [(‘D’,1),(‘o’,2),(‘g’,3)]
ghci> zipWith (/) [1,2,3] [4,5,6] [0.25,0.4,0.5]
ghci> myFlip (zipWith (/)) [1,2,3] [4,5,6] [4.0,2.5,2.0]
Note that zipWith (/) is a function that takes two arguments ghci> :t zipWith (/)
zipWith (/) :: Fractional c => [c] -> [c] -> [c]
Higher-Order Functions
Thumrongsak Kosiyatrakul
The map Function
The map function is provided by the standard library
Let’s look at its definition and try to understand how it works
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
map applies the given function to every element on the given list
ghci> map (*2) [1,2,3,4]
ghci> map (++ “!!!”) [“Dog”, “Cat”, “Fish”] [“Dog!!!”,”Cat!!!”,”Fish!!!”]
ghci> map fst [(1,5), (3,2), (4,1), (7,3)] [1,3,4,7]
Note that the result of map (*2) [1,2,3,4] is the same as [x * 2 | x <- [1,2,3,4]]
map tends to make code much more readable Higher-Order Functions
Thumrongsak Kosiyatrakul
程序代写 CS代考 加QQ: 749389476
The filter Function
Similarly, the filter function is provided by the standard
The filter function takes a predicate and a list, and returns the list of elements that satisfy that predicate
Try to come up with a definition...
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs) | p x = x : filter p xs
| otherwise = filter p xs
Here are some examples:
ghci> filter (<=10) [1..20]
[1,2,3,4,5,6,7,8,9,10]
ghci> filter even [1..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> filter (`elem` [‘A’..’Z’]) “Most Significant Bit” “MSB”
Higher-Order Functions
Thumrongsak Kosiyatrakul
The filter Function
To apply multiple predicates: Filtering multiple times
ghci> filter (<10) (filter even [1..20]) [2,4,6,8]
Join the predicate with the logical && function
ghci> let f x = x < 10 && even x in filter f [1..20]
How about another quick sort using filter?
quickSort [] = []
quickSort (x:xs) = sortedLessThanOrEq ++ [x] ++ sortedGreaterThan
where sortedLessThanOrEq = quickSort (filter (<= x) xs)
sortedGreaterThan = quickSort (filter (> x) xs)
Higher-Order Functions
Thumrongsak Kosiyatrakul
The filter Function
Exercise: Given positive integers d and n, find the largest number under d that is divisible by n
Example: Largest number under 100000 that is divisible by 97 is 99910
For simplicity, assume that d and n are positive and n < d
Try them all starting from d - 1 down to 1: [d-1,d-2..1]
The condition is mod by n is 0
Filter with the condition and get the first one only (head):
largest d n = head (filter p [d-1,d-2..1])
where p x = mod x n == 0
ghci> largest 100 97
ghci> largest 100000 97 99910
ghci> largest 100000 4971 99420
Higher-Order Functions
Thumrongsak Kosiyatrakul
The takeWhile Function
The takeWhile function takes a predicate and a list
Starting at the beginning of the list, it returns the list’s element as long as the predicate holds true
ghci> :t takeWhile
takeWhile :: (a -> Bool) -> [a] -> [a]
ghci> takeWhile (<'t') "I love Haskell"
ghci> takeWhile even [2,12,6,24,7,22,9,10] [2,12,6,24]
ghci> takeWhile (/=’ ‘) “What is the first word?” “What”
Higher-Order Functions
Thumrongsak Kosiyatrakul
The takeWhile Function
Exercise: Find the sum of all odd squares that are less than n Example: sum of all odd squares that are less than 30 is
12 +32 +52 =1+9+25=35
For simplicity generate all squares:
map (^2) [1,2..]
Filter just those that are ood:
filter odd (map (^2) [1,2..])
Take all elements start at the beginning until it is not less than a give number n:
takeWhile (
[5,16,8,4,2,1]
ghci> collatzSeq 11
[11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]
ghci> collatzSeq 27 [27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364, 182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263, 790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377, 1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238, 1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077, 9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122, 61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Collatz Sequence
Given a number n and an upperbound b, give a list all starting numbers between 1 and b of the Collatz sequences that has length greater than or equal to n
All starting numbers between 1 and b: [1..b]
Create the list of all Collatz sequences (from 1 to b): map collatzSeq [1..b]
Filter just those that has length greater than or equal to n: filter longerThan (map collatzSeq [1..b])
where longerThan xs = length xs >= n
Get the heads of all filtered sequences:
startNumbers n b = map head (filter longerThan
(map collatzSeq [1..b]))
where longerThan xs = length xs >= n
Higher-Order Functions
Thumrongsak Kosiyatrakul
List of Functions using map
Recall that if we partially apply a function, we get another function in return
max is a function
max 5 is another function
What is this expression?
map max [3,5,1,2,4]
It is a list of functions
[max 3, max 5, max 1, max 2, max 4]
Note that we cannot see the result on the screen since functions are not instances of the Show type class
However, the following is fine:
ghic> ((map max [3,5,1,2,4]) !! 1) 3 5
ghci> ((map max [3,5,1,2,4]) !! 1) 7 7
Higher-Order Functions
Thumrongsak Kosiyatrakul
Lambdas are anonymous functions (functions without names) We generally use a lambda when we need the function only once
Mathematical Syntax: 𝜆𝑥. 𝑓 (𝑥) Examples:
𝜆 𝑥. 𝑥 + 1 where (𝜆 𝑥. 𝑥 + 1) 5 is 6
𝜆 𝑥 𝑦. 𝑥 × 𝑦 where (𝜆 𝑥 𝑦. 𝑥 × 𝑦) 5 12 is 60
In Haskell, we use \ to represent lambda and -> instead of . Above examples in Haskell
ghci> (\x -> x + 1) 5
ghci> (\x y -> x * y) 5 12 60
Higher-Order Functions
Thumrongsak Kosiyatrakul
Recall the function startNumber defined earlier:
startNumbers n b = map head (filter longerThan
(map collatzSeq [1..b]))
where longerThan xs = length xs >= n
The function longerThan is used only once and only available inside the function definition
We can use the following instead:
startNumbers n b = map head (filter (\xs -> length xs >= n)
(map collatzSeq [1..b]))
Higher-Order Functions
Thumrongsak Kosiyatrakul
Lambdas are expressions: A lambda has a type
ghci> :t (\x y -> x + y)
(\x y -> x + y) :: Num a => a -> a -> a
Partially apply is allowed
ghci> :t (\x y -> x + y) 5
(\x y -> x + y) 5 :: Num a => a -> a
It can be passed as an argument
ghci> map (\x -> x + 1) [3,5,1,2,4] [4,6,2,3,5]
Higher-Order Functions
Thumrongsak Kosiyatrakul
A Lambda can take multiple arguments
ghci> zipWith (\x y -> x * y) [1,2,3,4] [3,7,1,2] [3,14,3,8]
A Lambda can take a pair as an argument
ghci> map (\(x,y) -> x * y) [(1,2), (3,4), (5,6), (7,8)] [2,12,30,56]
These three functions are equivalent:
ghci> addTwo x y = x + y
ghci> :t addTwo
addTwo :: Num a => a -> a -> a
ghci> addTwo’ = \x y -> x + y ghci> :t addTwo’
addTwo’ :: Num a => a -> a -> a
ghci> addTwo” = \x -> \y -> x + y ghci> :t addTwo”
addTwo” :: Num a => a -> a -> a
but the first one is easier to read Do not need to try to use lambdas
Higher-Order Functions
Thumrongsak Kosiyatrakul
Recall when we try to do something on a list
We need to decide what to do with the empty list Then handle non-empty list like x:xs
We do this with almost every function on lists
Haskell provides fold functions to handle these common pattern Folds allow you to reduce a list into a single value
Folds are suitable for operations that require to travel a list once, element-by-element
A fold takes the following arguments:
A binary function (a function that takes two arguments) A starting value
Higher-Order Functions
Thumrongsak Kosiyatrakul
To easily understand the left fold, let’s look at the definition of the foldl function:
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Sometime we call z as an accumulator
Let’s trace what is going on with foldl (+) 0 [1,2,3]
foldl (+) 0 [1,2,3] = foldl (+) 0 1:[2,3]
= foldl (+) (0 + 1) [2,3]
= foldl (+) (0 + 1) 2:[3]
= foldl (+) ((0 + 1) + 2) [3]
= foldl (+) ((0 + 1) + 2) 3:[]
= foldl (+) ((0 + 1) + 2) + 3) [] = (((0 + 1) + 2) + 3)
= ((1 + 2) + 3)
The list is folded from the left side
The binary function is applied between the starting accumulator and the head of the list
The result becomes the new starting value of the rest of the list
Higher-Order Functions
Thumrongsak Kosiyatrakul
Right Fold
To easily understand the right fold, let’s look at the definition of the foldr function:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Let’s trace what is going on with foldl (+) 0 [1,2,3]
foldr (+) 0 [1,2,3] = foldr (+) 0 1:[2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (foldr (+) 0 2:[3])
= 1 + (2 + (foldr (+) 0 [3]))
= 1 + (2 + (foldr (+) 0 3:[]))
= 1 + (2 + (3 + (foldr (+) 0 []))) = 1 + (2 + (3 + 0))
= 1 + (2 + 3)
The list is folded from the right side
The binary function is applied between the head of the list and the result of the rest of the fold
Higher-Order Functions
Thumrongsak Kosiyatrakul
Let’s Double Check
Let’s try to define our own map function called myMapr using foldr
Since the result of a map is a list, the accumulator should be the empty list
myMapr f xs = foldr g [] xs
where g y ys = f y : ys
Let’s try to define our own map function called myMapl using foldl
myMapl f xs = foldl g [] xs
where g ys y = ys ++ [f y]
Note that : will be a lot faster than ++ 1:[2,3] = [1,2,3]
[1,2] ++ [3] = 1:([2] ++ [3])
= 1:(2:[] ++ [3])
= 1:(2:[3])
Higher-Order Functions
Thumrongsak Kosiyatrakul
foldr vs foldl
What is foldr (:) [] [1..] evaluated to? ghci> foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9…Interrupted.
Let’s trace take 3 (foldr (:) [] [1..])
take 3 (foldr (:) [] [1..])
= take 3 (foldr (:) [] 1:[2..])
= take 3 ((:) 1 (foldr (:) [] [2..]))
= (:) 1 (take 2 (foldr (:) [] [2..]))
= (:) 1 (take 2 (foldr (:) [] 2:[3..]))
= (:) 1 (take 2 ((:) 2 (foldr (:) [] [3..])))
= (:) 1 ((:) 2 (take 1 (foldr (:) [] [3..])))
= (:) 1 ((:) 2 (take 1 (foldr (:) [] 3:[4..])))
= (:) 1 ((:) 2 (take 1 ((:) 3 (foldr (:) [] [4..])))) = (:) 1 ((:) 2 ((:) 3 (take 0 (foldr (:) [] [4..])))) = (:) 1 ((:) 2 ((:) 3 []))
We only need the first three element.
Higher-Order Functions
Thumrongsak Kosiyatrakul
Right Fold vs Left Fold
Let’s trace the foldr again with a binary function f
foldr f z [1,2,3]
= foldr f z 1:[2,3]
= f 1 (foldr f z [2,3])
= f 1 (foldr f z 2:[3])
= f 1 (f 2 (foldr f z [3]))
= f 1 (f 2 (foldr f z 3:[]))
= f 1 (f 2 (f 3 (foldr f z []))) = f 1 (f 2 (f 3 z))
Let’s trace the foldl again with a binary function f
foldl f z [1,2,3]
= foldl f z 1:[2,3]
= foldl f (f z 1) [2,3] = foldl f (f z 1) 2:[3] = foldl f (f (f z 1) 2) = foldl f (f (f z 1) 2) = foldl f (f (f (f z 1) = f (f (f z 1) 2) 3
Infoldr,f 1 …mayalreadyproduceapartialresult Right folds works on infinite lists but left folds do not
Higher-Order Functions
Thumrongsak Kosiyatrakul
foldl1 and foldr1 Let’s check their types:
ghci> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b ghci> :t foldl1
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a
ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b ghci> :t foldr1
foldr1 :: Foldable t => (a -> a -> a) -> t a -> a
foldl1 and foldr1 do not need a starting value
They use the first element (foldl1) and the last element
(foldr1) as their starting values
For foldl and foldr, their starting values do not have to have
the same type as elements in a given list
Higher-Order Functions
Thumrongsak Kosiyatrakul
Exercise with Folds
Let’s try to define the reverse function using foldl Initial value should be the empty list and we will slowly
accumulate it So, it should be
foldl f [] [1,2,3] for a function f
The above expression is evaluated to
foldl f (f [] 1) [2,3]
and eventually to
f (f (f [] 1) 2) 3
What should f be?
Higher-Order Functions
Thumrongsak Kosiyatrakul
Exercise with Folds
Obviously, f [] 1 should be [1] 1:[] = [1] or
[] ++ [1] = [1]?
To decide which one is correct, we need to consider the next application as well
Consider f (f [] 1) 2
If f [] 1 = 1:[]
f (f [] 1) 2 = f (1:[]) 2
If f [] 1 =[] ++ [1]
f (f [] 1) 2 = f ([] ++ [1]) 2
= [1] ++ [2]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Exercise with Folds
Obviously, f xs x should be x : xs
In other words, f should have type [a] -> a -> [a] Recall that : has type a -> [a] -> [a]
The first argument an element and The second argument is a list
Thus, we cannot use the : function directly We need to flip the arguments
Higher-Order Functions
Thumrongsak Kosiyatrakul
Exercise with Folds
Solution 1: Use a local binding
reverse_l1 lst = foldl f [] lst
where f xs x = x : xs
Solution 2: Use a Lambda:
reverse_l2 lst = foldl (\xs x -> x : xs) [] lst
Solution 3: Use the flip function: reverse_l3 lst = foldl (flip (:)) [] lst
Higher-Order Functions
Thumrongsak Kosiyatrakul
浙大学霸代写 加微信 cstutorcs
Exercise with Folds
How about foldr? At least it should be
foldr f [] [1,2,3] for a function f
The above expression is evaluated to
f 1 (foldr [] [2,3])
and eventually to
f 1 (f 2 (f 3 []))
What should f be?
In this case, f 3 [] should be [] ++ [3] = [3] Then f 2 [3] will be [3] ++ [2] = [3,2]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Exercise with Folds
Solution 1: Use a local binding
reverse_r1 lst = foldr f [] lst
where f x xs = xs ++ [x]
Solution 2: Use a Lambda:
reverse_l2 lst = foldr (\x xs -> xs ++ [x]) [] lst
Flip cannot be used since arguments have type a and [a] but ++ has type [a] -> [a] -> [a]
Higher-Order Functions
Thumrongsak Kosiyatrakul
scanl and scanr functions are the same as foldl and foldr
Instead of showing the final value, scans show immediate accumulators as a list
ghci> scanl (+) 0 [1,2,3] [0,1,3,6]
ghci> scanr (+) 0 [1,2,3] [6,5,3,0]
scanl1 and scanr1 are also available
They are good tools for debugging functions that utilize folds
Higher-Order Functions
Thumrongsak Kosiyatrakul
How many elements does it take for the sum of the square roots of all natural numbers to exceed 1000?
First, the list of square roots of all natural numbers:
map sqrt [1..]
Now, turn it into the list of immediate accumulators
scanl1 (+) (map sqrt [1..])
We will take all elements that are less than 1000
takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))
Now, the answer is the length of the above list
length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..])))
To go over 1000, you need to add one more square root:
length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Application using $
Consider the expression f a b c d
The expression f a b c d is (((f a) b) c) d
f a results in a new function
(f a) b results in a new function
In other words, function application is left associative The following expression
sum filter even [1..20]
will cause an errorbecause it tries to perform
((sum filter) even) [1..20]
We need parentheses:
sum (filter even [1..20])
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Application using $ $ is an infix function:
ghci> :t ($)
($) :: (a -> b) -> a -> b
It takes a function of type a -> b, a value of type a, and returns a value of type b
Consider the type of the function head ghci> :t head
head :: [a] -> a
Now,whatabout($) head? ghci> :t ($) head
($) head :: [b] -> b
They have the same type
What is the purpose of the ($) function then?
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Application using $
Function application with $ is right-associative In other words, f $ a b c d is f (a (b (c d)))
Note that (a (b (c d))) becomes one expression as the
argument to the function f
For simplicity you can think of f $ exp1 exp2 … expn as
f (exp1 exp2 … expn)
Use $ will result in less number of parentheses
For example, instead of
sum (filter even [1..20])
simply use
sum $ filter even [1..20]
Another example, instead of
sum (filter even (map (+3) [1..20]))
simply use
sum $ filter even $ map (+3) [1..20]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Composition
In mathematics, suppose 𝑓 and 𝑔 are functions, a function composition is defined as
( 𝑓 ◦ 𝑔)(𝑥) = 𝑓 (𝑔(𝑥))
To perform function composition in Haskell, we use the .
ghci> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
The definition of the . function is defined as f . g = \x -> f (g x)
Note that the type of the argument of the f function must be the same as the type of the value that returned by the g function
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Composition
We generally use function composition to make functions on the fly to pass to other functions
This is the same as one of the purpose of using lambda
Function composition is generally clearer and more concise
Example: Suppose we want to turn very number on a list to negative number
Use lambda:
map (\x -> negate (abs x)) [3,-5,1,2,-4]
Use function composition
map (negate . abs) [3,-5,1,2,-4]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Function Composition
Function composition is right-associative
f (g (h x)) is simply (f . g . h) x
ghci> map (negate . sum . tail) [[1,2,3],[4,1,5,6],[1,1,2,5]] [-5,-12,-8]
Higher-Order Functions
Thumrongsak Kosiyatrakul
Programming Help
Function Composition
For every function in composition, it cannot take multiple argument
To use a function that takes more than one arguments in a composition, we need to partially apply it
ghci> :t sum
sum :: (Foldable t, Num a) => t a -> a ghci> :t replicate
replicate :: Int -> a -> [a]
ghci> :t max
max :: Ord a => a -> a -> a
Instead of
ghci> sum (replicate 5 (max 5 12)) 60
we can use
ghci> (sum . replicate 5 . max 5) 12 60
replicate 5onlytakesoneargument max 5onlytakesoneargument
Higher-Order Functions
Thumrongsak Kosiyatrakul
Point-Free Style
Consider the following function mySum mySum xs = foldl (+) 0 xs
Because of currying, we can omit xs on both side mySum = foldl (+) 0
foldl (+) 0 is a function that take a list as the argument
Point-free style does not include information regarding its argument
Instead of 𝑓 (𝑥) = 𝑔(𝑥), we can simply say 𝑓 = 𝑔 Insteadof 𝑓(𝑔(𝑥)) = h(𝑥),wecansimplysay 𝑓 ◦𝑔 = h
Note that 𝑓 ◦ 𝑔 in mathematics is the same as f . g in Haskell Point-free style does not mean no point (.) in an expression Haskell use point (.) to represent ◦ in function composition
Higher-Order Functions
Thumrongsak Kosiyatrakul
Point-Free Style
Let’s consider another example:
fn x = ceiling (negate (tan (cos (max 50 x))))
We cannot simply remove x on both sides of the above expression cos (max 50) is an invalid expression
cos is a function that takes a number as an argument max 50 is a function
cos (max 50) 20 is also invalid
However, we can use function composition:
fn = ceiling . negate . tan . cos . max 50
Often time, a point-free style is more readable and concise Readers simply focus on just functions
It may not suitable for complex functions
Higher-Order Functions
Thumrongsak Kosiyatrakul