Before you begin
Why this matters
map, sortBy, and most of the Prelude take a function from you, and many functions you write will return one. If you can read the arrows in a type and tell a function from its result, you can predict what such code computes and read GHC’s errors when an argument is given too early or left out.
What this helps you reason about
- Follow a function you passed in: the function that received it applies it, once per element, when the result is needed.
- Read (Int -> Int) -> [Int] -> [Int] and Int -> (Int -> Int).
- Read “Couldn’t match expected type ‘Int -> Int’ with actual type ‘Int’” and “No instance for (Show …)”.
Haskell functions are values like any other: they are passed to functions and returned from them all the time. This lesson shows how a function applies a function it receives, how a function returns a new function, how to read a function type, and what GHC says when a function is applied where the function itself was needed.
Already know this? The short version
- applyToEach addBonus scores passes addBonus, and applyToEach applies it to each element when that element is needed; a function that takes or returns a function is a higher-order function.
- makeScorer :: Int -> (Int -> Int) returns a function; makeScorer 3 is computed once when it is first needed, and makeScorer 3 8 means (makeScorer 3) 8.
- Arrows group to the right, so the parentheses in Int -> (Int -> Int) can be left out; the parentheses in (Int -> Int) -> [Int] -> [Int] cannot, because they mark a function argument.
- An argument given too early gives “Couldn’t match expected type ‘Int -> Int’ with actual type ‘Int’”; one left out gives “No instance for (Show …)”.
Words in this lesson (4)
- higher-order function
- A function that takes a function as an argument, returns a function, or both.
- function type
- A type written with arrows, such as Int -> Int for a function from Int to Int. The arrow groups to the right, so Int -> Int -> Int means Int -> (Int -> Int).
- lambda
- A function written as a value, without a name, such as \glasses -> glasses + 1. The names after the backslash are its parameters.
- partial application
- Applying a function to fewer arguments than it takes, such as area 3. The result is a function that waits for the remaining arguments.
Examples are focused snippets; imports, enclosing functions, or classes may be omitted. C examples use C11; Haskell examples use Haskell 2010. Expand the notes for language-specific depth.
01 / Callbacks
How does a function accept behavior?
Function calls showed that a function is a value: applyTo triple 4 passes triple, and applyTo applies it. applyToEach below uses this for a list. Its first argument is a function, rule, and it applies rule to every element. It does not decide what to do with each score: whoever applies applyToEach passes that in.
A function that takes a function as an argument, or returns one, is called a higher-order function. applyToEach is a higher-order function. addBonus, which gives points + 2, is an ordinary function. With doublePoints instead, the same applyToEach doubles each score. In other languages, a function passed this way is often called a callback.
applyToEach is map from the Prelude, written out. sortBy works the same way: it takes a comparison function that decides which of two elements comes first, and Ordering, sorting, and comparators follows that function in detail.
applyToEach :: (Int -> Int) -> [Int] -> [Int]
applyToEach _ [] = []
applyToEach rule (points : rest) =
rule points : applyToEach rule rest
main :: IO ()
main = print (applyToEach addBonus [6, 8, 7]) -- [8,10,9]A higher-order function receives behavior as a function argument and decides where to apply it.
Coming from Python: map(add_bonus, scores) in Python is lazy too, but it can be used once only. A Haskell list built by applyToEach can be used as often as needed, and each element is computed at most once.
Precisely: applied only when needed
applyToEach rule rest is not computed when the first element is: each element is computed when print needs it. A function passed in is applied only as often as its results are demanded, which the first experiment shows as stops in applyToEach and addBonus taking turns.
Experiment
Follow a rule into the function that applies it
applyToEach receives the rule as a value and applies it to each element, as rule points. Which function is applied is decided by the caller, in applyToEach addBonus. applyToEach never names addBonus or doublePoints.
Why it matters To change what a higher-order function does with each item, change the function you pass to it. The higher-order function stays the same.
Predict the printed list, and in which order GHCi stops in applyToEach and addBonus. Then change applyToEach addBonus to applyToEach doublePoints, and predict again.
applyToEach :: (Int -> Int) -> [Int] -> [Int]
applyToEach _ [] = []
applyToEach rule (points : rest) = rule points : applyToEach rule rest
addBonus :: Int -> Int
addBonus points = points + 2
doublePoints :: Int -> Int
doublePoints points = points * 2
main :: IO ()
main = print (applyToEach addBonus [6, 8, 7])
What to look for
GHCi shows one location per stop, not a stack of frames. print needs the list, so GHCi stops in applyToEach with points 6 and rule _ (unevaluated): the function is passed along without being looked at. The output grows to [, then GHCi stops in addBonus with points 6, and the output grows to [8. Each element is computed when print needs it: applyToEach, then addBonus, then the next element. The run prints [8,10,9]. After the edit, the stops are in doublePoints, and the run prints [12,16,14]. applyToEach did not change.
Expected output
[8,10,9]02 / Factories
How does a function return new behavior?
A function can also return a function. makeScorer below takes a difficulty and returns a lambda that multiplies points by it. Its type, Int -> (Int -> Int), says so. A function that makes and returns a new function is often called a factory.
makeScorer 3 is computed once, the first time hard is needed, and the result is a function that keeps difficulty, as Closures and captured variables showed. Applying hard to 6 and to 8 uses that one function.
Application groups to the left: makeScorer 3 8 means (makeScorer 3) 8. It applies makeScorer to 3, then applies the resulting function to 8. That is why makeScorer can be used as if it took two arguments, and why makeScorer difficulty points = points * difficulty defines the same function.
makeScorer :: Int -> (Int -> Int)
makeScorer difficulty = \points -> points * difficulty
main :: IO ()
main = do
let hard = makeScorer 3
print (hard 6, hard 8) -- (18,24)
print (applyToEach (makeScorer 2) [6, 8, 7]) -- [12,16,14]A function can return a function. Name the result once, and apply it as often as needed.
Experiment
Make a scorer, then apply it
makeScorer 3 is computed once, the first time hard is needed, and the result is a function that keeps difficulty. Applying hard to 6 and to 8 uses that one function. makeScorer 3 8 means (makeScorer 3) 8: it computes makeScorer 3 again and applies the result to 8.
Why it matters Name the result of a factory when you need the same rule many times; it is computed once.
Predict the pair, and how many times GHCi stops in makeScorer before the lambda. Then change hard 8 to makeScorer 3 8, and predict again.
makeScorer :: Int -> (Int -> Int)
makeScorer difficulty = \points -> points * difficulty
main :: IO ()
main = do
let hard = makeScorer 3
print (hard 6, hard 8)
What to look for
The let line only names hard. When print needs hard 6, GHCi stops on the let line, named Main.main.hard, then in makeScorer with difficulty 3, then in the lambda, also named Main.makeScorer, with points 6 and difficulty 3. The output so far is (, then (18,. For hard 8, GHCi goes straight to the lambda: makeScorer 3 was computed once, and hard is that function. The run prints (18,24). After the edit, makeScorer 3 8 stops in makeScorer again, with difficulty 3, before the lambda with points 8, and the run still prints (18,24).
Expected output
(18,24)03 / Types
How do you write the type of a function?
A function type is written with arrows: Int -> Int takes an Int and gives an Int. The arrow groups to the right, so Int -> (Int -> Int) and Int -> Int -> Int are the same type, and every function of “two arguments” is a function that returns a function.
Parentheses on the left of an arrow are different. In (Int -> Int) -> [Int] -> [Int], the first argument is itself a function. Without the parentheses, Int -> Int -> [Int] -> [Int] would be a function of an Int, another Int, and a list.
A type can use type variables, as in Generics and type parameters. map’s type is (a -> b) -> [a] -> [b]: it takes any function and a list of that function’s argument type.
addBonus :: Int -> Int
-- the same type as Int -> (Int -> Int):
makeScorer :: Int -> Int -> Int
applyToEach :: (Int -> Int) -> [Int] -> [Int]
map :: (a -> b) -> [a] -> [b]Arrows group to the right; parentheses on the left of an arrow mark an argument that is a function.
Precisely: sections
(+ 2) and (* 3) are sections: an operator with one side given, which is a function waiting for the other side. applyToEach (+ 2) [6, 8, 7] gives [8,10,9]. (- 2) is not a section, because Haskell reads it as the number minus two; subtract 2 is the function.
04 / Pass or call
What goes wrong when a function is applied instead of passed?
Writing a function’s name alone passes the function. Applying it to an argument passes its result. Mixing the two up is the most common mistake with higher-order functions, and GHC catches both directions.
An argument given too early: describe (addBonus 8) passes the Int 10, where describe needs a function. GHC reports: Couldn’t match expected type ‘Int -> Int’ with actual type ‘Int’, with the line Possible cause: ‘addBonus’ is applied to too many arguments.
An argument left out: print (applyToEach addBonus) asks print to show a function that still waits for its list. GHC reports No instance for (Show ([Int] -> [Int])), and asks: maybe you haven’t applied a function to enough arguments?
describe :: (Int -> Int) -> String
describe rule = "8 becomes " ++ show (rule 8)
main = putStrLn (describe addBonus) -- 8 becomes 10
-- describe (addBonus 8): Couldn't match expected type
-- print (applyToEach addBonus): No instance for (Show ...)An Int where a function was expected means an argument came too early; a function that cannot be shown means an argument is missing.
Experiment
Apply a function where the function was expected
addBonus 8 is an Int, and describe needs a function from Int to Int. The other direction is caught as well: print (applyToEach addBonus), with the list left out, gives No instance for (Show ([Int] -> [Int])), and GHC asks whether a function was applied to enough arguments.
Why it matters When GHC finds an Int where it expected Int -> Int, an argument was given too early. When it cannot show a function, an argument is missing.
Predict the printed line. Then change describe addBonus to describe (addBonus 8), and read what the compiler says.
describe :: (Int -> Int) -> String
describe rule = "8 becomes " ++ show (rule 8)
addBonus :: Int -> Int
addBonus points = points + 2
main :: IO ()
main = putStrLn (describe addBonus)
What to look for
GHCi stops in describe, and the output grows to “8 becomes ” before addBonus is needed: putStrLn prints the text as it is demanded. Then GHCi stops in addBonus with points 8, and the run prints 8 becomes 10. After the edit, GHCi refuses to load the program: Couldn’t match expected type ‘Int -> Int’ with actual type ‘Int’, with the line Possible cause: ‘addBonus’ is applied to too many arguments.
Expected output
8 becomes 1005 / Try it
Can you follow behavior passed in and returned?
One function is passed, one is built by a factory, and one application gives a function. Decide what each one computes.
applyTwice :: (Int -> Int) -> Int -> Int
applyTwice rule points = rule (rule points)
makeScorer :: Int -> (Int -> Int)
makeScorer difficulty = \points -> points * difficulty
addBonus :: Int -> Int
addBonus points = points + 2
main :: IO ()
main = do
let a = applyTwice addBonus 5
b = applyTwice (makeScorer 2) 3
putStrLn (show a ++ " " ++ show b)
What is printed?
Reveal the reasoning
9 12. applyTwice applies the function it receives two times, the second time to the first result. addBonus turns 5 into 7, then 9. makeScorer 2 is a function that doubles: 3 becomes 6, then 12. The parentheses around makeScorer 2 make it one argument; without them, applyTwice would receive makeScorer, 2, and 3.
Practice tickets
- HOF-101 · The board shows each athlete’s worst result as their best → Free
- HOF-102 · Every win counts as a first-round win → Sign in · Pro
- HOF-103 · Practice marks fall below zero or stay above the scale → Sign in · Pro