Before you begin
Why this matters
A Haskell module is a set of definitions, and readers from other languages read them as steps. If you read each = as an equation, you can predict a result from what each definition uses, spot a definition that uses its own name by mistake, and say when a value is computed and how many times.
What this helps you reason about
- Predict a program’s result whatever the order of its definitions.
- Spot a definition that uses its own name where an update was meant.
- Say when a binding is computed, and whether it is computed once or again.
In Python, Java, or JavaScript, = is a step: it stores a value now, and x = x + 1 adds one to the old value. Haskell has no such step. Variables showed that a Haskell binding is a name for a value and is never assigned again. This lesson looks closely at what = means instead, and at what follows from it: definitions in any order, definitions that use each other, and a line that looks like an update but never finishes.
Already know this? The short version
- = states an equation: the name means the expression everywhere in its scope. The definitions of a module, a where, or a let can come in any order and can all use each other.
- A definition that uses its own name is recursive. That is useful for a function that reaches an equation without itself; a value such as let kilos = kilos + 5 never finishes, and a compiled program often stops with <<loop>>.
- A where belongs to one equation and is shared by its guards, which are tried from top to bottom; let … in belongs to one expression.
- A binding is computed when it is first needed, and GHC then keeps the result, so it is computed once; a pattern binding is matched when one of its names is needed. The section “What goes wrong with bindings in real programs?” covers a self-reference meant as an update, a where binding rebuilt on every call, the waiting additions of foldl, and a pattern binding that fails only when used.
Words in this lesson (8)
- binding
- A name given to a value by a definition such as count = 3. A binding never changes after it is defined.
- recursive definition
- A definition whose right side uses the name it defines. A recursive function can give a result; a value defined as total = total + 1 never does.
- equation
- One line of a function definition, such as countdown 0 = putStrLn "liftoff". GHC tries a function’s equations from top to bottom and uses the first one that matches.
- mutual recursion
- Two or more definitions that use each other, such as atHarbour using atBeach and atBeach using atHarbour.
- guard
- A Boolean test after |, such as | n <= 0. It is checked after the pattern matches and chooses which right-hand side to use.
- where clause
- Bindings written after where at the end of an equation. They can be used anywhere in that equation, including its guards.
- thunk
- GHC’s stored description of work that has not happened yet. When the value is needed, GHC runs the work and replaces the thunk with the result.
- pattern binding
- A binding whose left side is a pattern rather than one name, such as (minutes, seconds) = 200 `divMod` 60 in a let or where. Its pattern is matched only when one of its names is needed.
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 / Equations
What does = say in Haskell?
In Haskell, = states an equation: the name on the left means the expression on the right, everywhere in its scope. total = flight + apartment is not a step that runs at one moment. It is a fact about total, and it holds wherever total is used.
Because each definition is a fact, the order of definitions does not matter: at the top level of a module, in a where, and in a let. GHC computes a value when something needs it, and follows what each definition uses. Below, total is written above apartment and nights, and total still means 360.
total :: Int
total = flight + apartment
apartment :: Int
apartment = nights * 80
nights :: Int
nights = 3
flight :: Int
flight = 120
-- total is 360= states what a name means, everywhere in its scope; the order of definitions decides nothing.
Coming from Python: Python raises NameError for a name whose line has not run yet. A Haskell definition can be used above the line that defines it.
Precisely: the order in a do block
A do block lists actions, and actions run in the order they are written. So a name from a let in a do block can be used only on the lines after that let. The bindings inside one let are still a group, in which order does not matter. The Haskell 2010 Report sorts the bindings of a group by what each one uses before it works out their types; this is called dependency analysis.
Experiment
Follow definitions written in any order
Each definition states what a name means. GHC computes a name when something needs its value: main needs total, total needs flight and apartment, and apartment needs nights. The position of a definition in the file decides nothing.
Why it matters Read a Haskell module as a set of facts. To find the order of work, follow what each definition needs, starting from main.
total is defined above the names it uses. Predict which definition the stepper visits after total. Then change total = flight + apartment to total = apartment + flight and predict the order again.
main :: IO ()
main = print total
total :: Int
total = flight + apartment
apartment :: Int
apartment = nights * 80
nights :: Int
nights = 3
flight :: Int
flight = 120
What to look for
The stops are on line 2 (main), line 5 (total), line 14 (flight), line 8 (apartment), and line 11 (nights). Each stop shows one place, such as Main.total, not a list of frames. The run prints 360. flight comes before apartment because + on Int computes its left side first in this build, not because of the order in the file. After the edit, the stops are lines 2, 5, 8, 11, and 14, and the run still prints 360.
Expected output
36002 / Self-reference
What does a definition that uses its own name mean?
A definition can use the name it defines. This is a recursive definition. For a function, it is the usual way to repeat work: the function uses itself on a smaller argument, and one equation, for the smallest argument, gives the answer without using itself. Recursion covers recursive functions in detail.
For a value that is not a function, a recursive definition is usually a mistake. let kilos = kilos + 5 says that kilos is 5 more than itself. No number fits. To compute kilos, GHC first needs kilos, so the work never ends.
The kilos on the right is not the one from an earlier line. A let and a where each make a group, and a name is visible everywhere in its group, also on its own right side. So the new kilos hides the old one there too. Give the changed value a new name instead, such as packed.
main :: IO ()
main = do
let kilos = 18 :: Int
let packed = kilos + 5 -- a new name: 23
-- let kilos = kilos + 5 would never finish
print packedA value defined by itself never gets a value; give a changed value a new name.
Coming from JavaScript: x = x + 1 reads the old x and stores a new one. In Haskell, let x = x + 1 defines x by itself and never gives a value.
Precisely: <<loop>> and useful recursive values
While GHC computes a value, it can mark the value as being computed. When the same computation needs that value again, the runtime may see the cycle and throw the NonTermination exception, which prints <<loop>>. The runner’s compiled programs stopped this way, but the detection is not promised, and the stepper’s GHCi runs the edit until the 20 second limit. A recursive value is useful when its definition gives part of the value before it needs itself: trips = "harbour" : "beach" : trips is an endless list, and take 3 trips is ["harbour","beach","harbour"].
Experiment
Define a value by itself
A let makes a group in which every name is visible, also on its own right side. After the edit, the kilos on the right of line 4 is the new kilos, not the one from line 3. To compute kilos, GHC first needs kilos, so the work never ends.
Why it matters A changed value needs a new name. A line that looks like an update, x = x + 1, defines x by itself.
Predict what is printed. Then change line 4 to let kilos = kilos + 5 and line 5 to print kilos, and predict what happens.
main :: IO ()
main = do
let kilos = 18 :: Int
let packed = kilos + 5
print packed
What to look for
The stepper stops on line 2, then on line 5, where packed shows _ (unevaluated): a name whose value has not been computed yet. print needs packed, so the next stop is line 4, Main.main.packed, where kilos shows _ (unevaluated). packed needs kilos, so the last stop is line 3, and the run prints 23. After the edit, the stepper stops on line 2, then on line 5 with kilos shown as _ (unevaluated), then on line 4. No further stop comes, nothing is printed, and the run ends with Stopped at the 20 second execution limit.
Expected output
2303 / Mutual recursion
Can two definitions use each other?
Every definition in a group can use every other one: all the top-level definitions of a module, or all the bindings of one let or where. So two definitions can use each other. This is mutual recursion.
A boat runs between the harbour and the beach, and starts at the harbour. atHarbour :: Int -> Bool says that atHarbour takes an Int, the number of trips, and gives a Bool, True or False. After 0 trips, the boat is at the harbour. After more trips, it is at the harbour if it was at the beach one trip earlier, and the other way round.
Each function is written as equations, one per line, and GHC uses the first one whose pattern matches: 0 matches only 0, and trips matches any number. Each function has an equation for 0 that answers without the other one, and each other equation uses a smaller number. So every application ends.
atHarbour :: Int -> Bool
atHarbour 0 = True
atHarbour trips = atBeach (trips - 1)
atBeach :: Int -> Bool
atBeach 0 = False
atBeach trips = atHarbour (trips - 1)
-- atHarbour 3 is False: the boat is at the beachDefinitions in one group can use each other in any order; every path must reach an equation that answers without the others.
Precisely: type checking a group
Definitions that use each other are type-checked together, so a type mistake in one can be reported at the other. A type signature on each definition, as here, keeps each message closer to its mistake.
Experiment
Follow two definitions that use each other
atHarbour uses atBeach, and atBeach uses atHarbour. Both are top-level definitions, so each is visible in the other. Every application uses a smaller number, so one of the 0 equations is always reached, and it answers without the other function.
Why it matters Definitions in one group may use each other in any order. Check that every path reaches an equation that answers without the others.
The boat starts at the harbour. Predict where it is after 3 trips, and which lines the stepper visits. Then change main to print (atBeach 3) and predict again.
atHarbour :: Int -> Bool
atHarbour 0 = True
atHarbour trips = atBeach (trips - 1)
atBeach :: Int -> Bool
atBeach 0 = False
atBeach trips = atHarbour (trips - 1)
main :: IO ()
main = print (atHarbour 3)
What to look for
After two stops on line 10, the stepper alternates: line 3 with trips 3, line 7 with trips 2, line 3 with trips 1. Each of these lines appears twice in a row, because GHCi also stops where trips - 1 is computed. The last stop is line 6, the equation atBeach 0 = False, which has no name to show. The run prints False. After the edit, the stops are line 7 with trips 3, line 3 with trips 2, line 7 with trips 1, and then line 2, atHarbour 0 = True. The run prints True.
Expected output
False04 / let and where
Where do let and where put their definitions?
Scope and shadowing showed that where covers a whole equation, and let … in covers one expression. Both make a group, so the rules above hold for both: any order, and every name visible in the whole group, including its own definition.
A guard lets one equation give different results. Each guard is a test after |, followed by = and the result for that case. GHC checks the guards from top to bottom and uses the first one that is True. otherwise is always True, so it catches every other case. The bindings in where can use the parameters, and every guard and result can use them.
A where belongs to one equation. When a function has several equations, a where after the last one cannot be used in the others. let … in is an expression, so it can sit inside one result, and its names can be used only there.
rentLine :: Int -> String
rentLine days
| days >= 7 = "week rate: " ++ show (perDay - 1)
| otherwise = "day rate: " ++ show perDay
where
perDay = lounger + umbrella
lounger = 6
umbrella = 2
-- rentLine 7 is "week rate: 7"A where belongs to one equation and is shared by all its guards; let … in belongs to one expression.
05 / Demand
When is a binding computed, and how many times?
A binding is computed when something needs its value, not when its line is reached. This is non-strict evaluation, which Variables introduced. GHC keeps the work for a value that has not been computed yet as a thunk. When the value is needed, GHC does the work and replaces the thunk with the result.
So GHC computes a binding at most once. Every later use of the name reads the stored result. Below, ticket is used twice, and fare runs once. With fare 4 written twice instead, fare runs twice: GHC does not promise to notice that two expressions are the same.
The same holds for a where binding that several guards use. It is computed when the first guard or result needs it, and never if none does. A pattern binding such as (stay, cost) = plan 3, where plan 3 gives a pair, is matched when stay or cost is first needed, as Destructuring and multiple bindings showed, and plan 3 is computed once for both names.
fare :: Int -> Int
fare people = people * 3 + 2
main :: IO ()
main = do
let ticket = fare 4
print (ticket + ticket) -- fare runs once: 28A binding is computed the first time its value is needed and then shared by every use; an expression written twice may be computed twice.
Coming from Java: A Java local variable is computed when its line runs, even if nothing reads it later. A Haskell binding is computed when its value is first needed, and then kept.
Precisely: sharing is GHC’s practice
The Haskell Report says when a value may be needed, not how often it is computed. Computing a named value once is what GHC does. With optimization, GHC may also notice that fare 4 + fare 4 repeats itself and compute it once; do not rely on it either way.
Experiment
Count how often a shared binding is computed
The first use of ticket computes fare 4 and keeps the result in place of the waiting work. The second use reads that result. Two expressions written separately are two pieces of work; GHC does not promise to notice that they are the same.
Why it matters Give a value a name when it is used more than once, and it is computed once. Writing the same expression twice can do the work twice.
ticket is used twice. Predict how many times the stepper enters fare. Then change line 7 to print (fare 4 + fare 4) and predict again.
fare :: Int -> Int
fare people = people * 3 + 2
main :: IO ()
main = do
let ticket = fare 4
print (ticket + ticket)
What to look for
The stepper stops on line 7 twice with ticket shown as _ (unevaluated), then on line 6, Main.main.ticket, then twice on line 2, Main.fare with people = 4: GHCi stops once for each part of people * 3 + 2. That pair of stops on line 2 comes once, and the run prints 28. After the edit, the pair of stops on line 2 comes twice, once for each fare 4, and the run still prints 28. ticket is no longer listed, because nothing uses it.
Expected output
2806 / In production
What goes wrong with bindings in real programs?
Four mistakes with bindings are common in real Haskell code.
A self-reference meant as an update. let total = total + fee reads like adding a fee, in a do block or in a where. It defines total by itself, so the program stops with <<loop>> or never finishes, often far from that line. Give the new value a new name. GHC’s -Wall option warns when the new total hides an earlier one.
A where binding rebuilt on every call. A table built in the where of a function that runs once per item is built again for each item, even when it uses no parameter. Move it to the top level, where it is computed once. GHC’s optimizer sometimes moves it for you; do not rely on that.
A lazy running total. foldl (+) 0 adds up a list from the left; (+) is + used as a function. Each addition waits in a thunk until the end, so a long list keeps one thunk per element. foldl' from Data.List computes each running total at once. A running total kept in a pair or a record has the same problem one level down.
A pattern binding that fails only when used. words splits text at spaces. The where below works for "Lisbon Portugal". For "Rio de Janeiro Brazil", the program stops with Non-exhaustive patterns in [city, country], and only where city or country is needed. Match each shape with case instead.
placeLabel :: String -> String
placeLabel place = city ++ " in " ++ country
where
[city, country] = words placeGive an update a new name, build fixed tables once, force a running total, and match every shape a value can have.
Experiment
Count how often a where binding is computed
A where binding belongs to one application of its function. Each application of hire makes a new rate, even though rate uses no parameter. A top-level binding belongs to the whole program, so it is computed once and shared by every application.
Why it matters Put a value that does not depend on the parameters at the top level when the function runs many times. Do not count on the optimizer to move it there.
hire is applied twice. Predict how many times the stepper stops on line 4. Then delete lines 3 and 4, add three lines at the top of the file, rate :: Int, rate = sum [2, 1, 1], and an empty line, and predict again.
hire :: Int -> Int
hire days = days * rate
where
rate = sum [2, 1, 1] -- lounger, umbrella, towel
main :: IO ()
main = print (hire 10 + hire 25)
What to look for
After three stops on line 7, the stepper stops on line 2 with days = 10 and rate shown as _ (unevaluated), then on line 4, Main.hire.rate. For hire 25, the same two stops come again: rate is unevaluated and computed a second time. The run prints 140. After the edit, main is on line 8 and hire’s equation on line 5. The stepper stops on line 2, Main.rate, after the first stop in hire only. For the second application, the stop in hire is the last one, because rate already has its value. The run still prints 140.
Expected output
14007 / Try it
Can you predict what each name means?
Find what each name means, and which names are ever needed, before you predict.
bagLabel :: Int -> String
bagLabel nights
| bags > 1 = show bags ++ " bags"
| otherwise = "hand luggage only"
where
bags = 1 + extra
extra = nights `div` 7
main :: IO ()
main = do
let trip = 15
(short, long) = (bagLabel 3, bagLabel trip)
spare = spare + 1 :: Int
putStrLn long
putStrLn short
What does the program print, and does it finish?
Reveal the reasoning
3 bags, then hand luggage only, and the program finishes. long is printed first, because its putStrLn comes first in the do block; the pattern binding is matched when long is needed. For 15 nights, extra is 15 `div` 7, which is 2, so bags is 3 and the first guard is True. For 3 nights, extra is 0 and bags is 1, so otherwise gives hand luggage only. bags uses extra, which is written below it; the order does not matter. spare is defined by itself and would never finish, but nothing needs spare, so it is never computed.
Practice tickets
- HS-101 · Express visa requests never get a price → Free
- HS-102 · Trip summaries stop at every day trip → Sign in · Pro
- HS-103 · The quote screen stops at a currency the desk does not trade → Sign in · Pro