Before you begin
Why this matters
Readers who know loops often know exactly what they want to repeat and not how to write it in Haskell. If you know which Haskell form matches each kind of loop, you can write the repetition you have in mind, read other people’s helper functions, and spot the mistakes that make one stop with an error or use too much memory.
What this helps you reason about
- Translate a while loop, a for-each loop, a counting loop, and a loop with break into Haskell.
- Predict which elements of a list a repetition ever looks at.
- Spot a list function with no answer for an empty list, and a running total that waits.
In Python, Java, or C, a loop keeps a counter such as i and changes it on every pass: While loops and termination, For loops and iteration protocols, and Break, continue, and early return follow those loops. Haskell has no loop statement, and a binding cannot be changed. This lesson takes each kind of loop in turn and shows what Haskell writes instead.
Already know this? The short version
- A while loop becomes a helper function: each value the loop changes is a parameter, each pass is an application with new arguments, and the stop condition is an equation or guard that does not use the helper again.
- For each element: map computes new values, and mapM_ or forM_ runs an action; zip [1 ..] adds positions, and replicateM_ n repeats an action n times.
- A total or a count is a fold: foldr f z, or foldl' for a strict running total, with z as the answer for []; sum and length are named folds.
- An early exit is an equation whose result does not use the function again; find gives the first match as a Maybe, takeWhile stops at the first failure, and until repeats without a list.
- The section “What goes wrong with repetition in real programs?” covers a running total that waits, no equation for [], results thrown away by forM_ and mapM_, and a list walked twice with length and !!.
Words in this lesson (8)
- accumulator
- An argument that carries a result from one recursive call to the next, such as a running total.
- base case
- The case, an input or a condition such as the pattern 0 or the guard n <= 0, that the function answers without using itself. Reaching it stops the recursion.
- recursive case
- An input the function answers by using itself on a smaller input.
- map
- An operation that applies a function to every element of a collection and gives the results in a new collection: one result per element, in the same order.
- mapM_
- A function that runs an action for each element of a list, in order, and keeps none of the results. forM_ from Control.Monad is the same function with its two arguments swapped.
- fold
- An operation that combines all elements of a collection into one value. It starts from a start value and applies a function to the result so far and each element in turn; for an empty collection it gives the start value.
- strict left fold
- foldl' from Data.List. It walks a list from the left and computes the running result at each step, so no additions wait.
- non-exhaustive patterns
- Patterns that do not cover every possible value. GHC accepts them; a value that matches none stops the program with Non-exhaustive patterns when it 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 / Loop state
What takes the place of a loop counter?
A while loop keeps its state in variables, such as a counter and a total, and changes them on every pass. A Haskell binding cannot change. Assignment and reassignment showed what replaces a running total: an accumulator, an argument that carries a result from one recursive call to the next.
The same idea translates a whole loop. Each value that the loop changes becomes a parameter of a helper function. Each pass is one application of the helper, with the new values as arguments. The stop condition becomes the base case: an equation or a guard that answers without using the helper again. Every other case is a recursive case, which uses the helper again with a smaller list or a value closer to the stop.
Below, daysUntil counts the school days until a class has had 6 absences in all. total and days are the loop state. There are two ways to stop: the guard, when the limit is reached, and the [] equation, when the days run out.
daysUntil :: Int -> Int -> [Int] -> Int
daysUntil total days [] = days
daysUntil total days (absent : rest)
| total >= 6 = days
| otherwise = daysUntil (total + absent) (days + 1) rest
-- daysUntil 0 0 [2, 1, 3, 5] is 3Each value a loop changes becomes a parameter, and each pass becomes one application with new arguments.
Coming from Java: A Java while loop changes i and total in place. In Haskell, i and total are parameters, and the next pass is the next application, with i + 1 and the new total as arguments.
Precisely: hiding the start values
A caller should not need to know that total and days start at 0. Put the helper in a where clause and give the outer function only the list: absentDays week = go 0 0 week, with go defined in the where. go is a common name for such a helper. The helper is still an ordinary recursive function.
Experiment
Follow the loop state through a recursive helper
total and days are the state that a loop would change. Here they are parameters, and each application has its own. The guard and the [] equation are the two ways to stop. The arguments of the next application are the new state. total is computed at each step because the guard needs it; nothing needs days until the end.
Why it matters To translate a while loop, list what changes on each pass. Each of those becomes a parameter, and each pass becomes one application with new arguments.
daysUntil counts school days until the class has had 6 absences in all. Predict what is printed. Then change 6 on line 4 to 20 and predict which equation gives the answer.
daysUntil :: Int -> Int -> [Int] -> Int
daysUntil total days [] = days
daysUntil total days (absent : rest)
| total >= 6 = days
| otherwise = daysUntil (total + absent) (days + 1) rest
main :: IO ()
main = print (daysUntil 0 0 [2, 1, 3, 5])
What to look for
GHCi shows one location per stop, not a stack of frames, and _ (unevaluated) for a value that is not computed yet. Each application stops on line 4 for the guard, then on line 5 with its own absent, rest, and total: 0, then 2, then 3. When the guard needs a new total, a stop on line 5 computes total + absent first. When total is 6, the guard on line 4 is True, but days still shows _ (unevaluated): the days + 1 additions waited. Three more stops on line 5 compute them, and the run prints 3. After the edit, the guard is never True. A stop on line 5 shows rest = [] and total 6, then the stepper stops on line 2, the [] equation. Four stops on line 5 compute days, and the run prints 4.
Expected output
302 / For each
How do you do something with each element?
map applies a function to every element of a list and gives the results in a new list, one per element, in the same order. map (28 -) week gives the number of pupils absent each day: (28 -) is an operator section: - with its left side filled in, so (28 -) 26 is 2. map computes values. It runs no actions.
To do something for each element, such as print a line, use mapM_. mapM_ report week runs report for each day, in order, and keeps none of the results. forM_ from Control.Monad is mapM_ with its two arguments swapped. It reads like a for loop when the body is written in place as a lambda: \(day, present) -> … is a function without a name, and its parameter is a pair. To run one action several times, replicateM_ 3 action, also from Control.Monad, runs it 3 times.
To know each element’s position, pair the elements with numbers. [1 ..] is the list 1, 2, 3, … with no end. zip makes pairs from two lists and stops at the end of the shorter one, so zip [1 ..] week gives (1, 26), (2, 24), (3, 27). No counter is needed.
import Control.Monad (forM_)
main :: IO ()
main = do
let week = [26, 24, 27] :: [Int]
print (map (28 -) week) -- [2,4,1]
forM_ (zip [1 ..] week) (\(day, present) ->
putStrLn ("day " ++ show day ++ ": " ++ show present))
-- day 1: 26, day 2: 24, day 3: 27map gives new values; mapM_ and forM_ run an action for each element; zip [1 ..] adds positions.
Coming from Python: for i, x in enumerate(xs) becomes forM_ (zip [0 ..] xs) …. enumerate counts from 0, so write [0 ..] to match it.
Coming from JavaScript: forEach runs a function for each element; in Haskell that is mapM_. map with an action gives a list of actions and runs none of them.
Precisely: mapM_ beyond lists and IO
mapM_ and forM_ work for any Foldable container, such as a Maybe or a Data.Map, and for any Monad, not only IO. Their types in base are mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m (). The m () at the end is why no results are kept.
Experiment
Print one line for each day with mapM_
mapM_ report week is one IO action. It runs report 26, then report 24, then report 27, in order, and keeps no results. map report week is a list of three actions, of type [IO ()]. A list is a value, not an action, so a line of a do block cannot run it.
Why it matters Use map to compute new values. Use mapM_ or forM_ to run an action for each element.
Predict the lines printed before week done. Then change mapM_ on line 7 to map and predict what happens.
report :: Int -> IO ()
report present = putStrLn (show (28 - present) ++ " absent")
main :: IO ()
main = do
let week = [26, 24, 27]
mapM_ report week
putStrLn "week done"
What to look for
At line 7, week shows _ (unevaluated); the next stop, Main.main.week on line 6, computes it. GHCi then stops on line 2 four times for each day, with present 26, then 24, then 27, as it computes the parts of that line. Each day’s line, such as 2 absent, appears in the output before the stops for the next day. The last stop is on line 8, and the run prints week done. After the edit, the program does not compile. GHCi reports Main.hs:7:3: error: Couldn't match type ‘[]’ with ‘IO’, with Expected: IO (IO ()) and Actual: [IO ()]. Nothing runs.
Expected output
2 absent
4 absent
1 absent
week done03 / Totals
How do you add up or count a list?
A loop that adds up or counts combines all the elements into one value. That operation is a fold. foldr (+) 0 [26, 24, 27] is 26 + (24 + (27 + 0)): the start value 0 takes the place of [], so it is also the answer for an empty list. foldl' from Data.List works from the left and computes the running result at each step, like the accumulator in daysUntil. It is the strict left fold, and the one to use for a running total.
Common folds have names: sum adds, length counts the elements, and maximum and minimum find the largest and smallest. maximum and minimum have no start value, so they fail on []. To count only some elements, put the test into the fold’s function, as countLow does. Map, filter, and reduce compares the folds in more detail.
import Data.List (foldl')
total :: [Int] -> Int
total week = foldl' (+) 0 week -- total [26, 24, 27] is 77
countLow :: [Int] -> Int
countLow week = foldr step 0 week
where
step present count
| present < 25 = count + 1
| otherwise = count
-- countLow [26, 24, 27, 23] is 2A total or a count is a fold: a function that combines each element with the result so far, and a start value that is the answer for [].
Precisely: sum in older GHC versions
In the stepper’s GHC 9.0, sum is a lazy left fold and can build up waiting additions on a long list. From GHC 9.2 on, sum is strict. foldl' (+) 0 is strict in every version.
04 / Stopping
How do you stop early, or repeat until something is true?
A loop with break stops at the first element that matters. In a recursive function, the early exit is an equation or a guard whose result does not use the function again. firstLow below stops at the first day with fewer than 25 pupils. Nothing asks for the rest of the list, so the rest is never looked at.
The library has this shape too. find (< 25) week, from Data.List, gives Just 24 for [26, 24, 27, 23]: the first element that passes the test. When none passes, it gives Nothing. Just and Nothing are the two forms of a Maybe value. (< 25) is < with its right side filled in, so (< 25) 24 is True.
For “repeat until”, takeWhile (>= 25) week keeps the elements up to the first one that fails the test: [26]. filter (>= 25) week does not stop. It keeps every element that passes, anywhere in the list: [26, 27]. To repeat without a list, until test step start applies step until test is True: until (>= 100) (* 2) 3 doubles 3 until the result is at least 100, and gives 192.
firstLow :: [Int] -> String
firstLow [] = "no low day"
firstLow (present : rest)
| present < 25 = "first low day: " ++ show present
| otherwise = firstLow rest
-- firstLow [26, 24, 27, 23] is "first low day: 24"Stop early with an equation that does not use the function again; takeWhile stops at the first failure, and filter never stops early.
Coming from Java: Java leaves a loop with break. In Haskell there is nothing to leave: the equation that answers simply does not use the function again.
Precisely: stopping on an endless list
Because evaluation is non-strict, find and takeWhile look at elements only until they have their answer, so they work on an endless list: takeWhile (< 4) [1 ..] is [1,2,3]. filter cannot know that no later element passes. Printing filter (< 4) [1 ..] shows [1,2,3 and then never finishes.
Experiment
Stop at the first day below 25 pupils
The result of the first guard does not use firstLow. When that guard is True, the repetition ends there. Nothing asks for the rest of the list, so 27 and 23 are never looked at.
Why it matters An early exit is an equation or a guard whose result does not use the function again. find and takeWhile are written this way.
Predict which values present takes before the run ends. Then change 25 on line 4 to 20 and predict again.
firstLow :: [Int] -> String
firstLow [] = "no low day"
firstLow (present : rest)
| present < 25 = "first low day: " ++ show present
| otherwise = firstLow rest
main :: IO ()
main = putStrLn (firstLow [26, 24, 27, 23])
What to look for
The stepper stops on line 4 with present 26, then on line 5 with rest = [24,27,23], then on line 4 with present 24. That stop comes three times, and on the third the output already shows first low day: before show present is computed. 27 and 23 never appear as present. The run prints first low day: 24. After the edit, present takes all four values, a stop on line 5 shows rest = [], and the last stop is on line 2, the [] equation. The run prints no low day.
Expected output
first low day: 2405 / Recursion or a library function
When is plain recursion clearer than map or a fold?
map, mapM_, the folds, find, and takeWhile each name one common shape of repetition. When one of them fits, use it. A reader sees the shape from the name, and the base case is already written and tested.
Write the recursion yourself when no name fits. Common cases are a step that needs two neighbouring elements at once, a stop that depends on the state so far, as in daysUntil, and two results built at the same time. changes below compares each day with the next one. In its result, x : list puts x in front of list. The last equation, changes _ = [], covers both a list with one element and the empty list.
changes :: [Int] -> [Int]
changes (first : second : rest) =
(second - first) : changes (second : rest)
changes _ = []
-- changes [26, 24, 27] is [-2,3]Use a named function when its shape fits; write the recursion when a step needs more than one element or a state of its own.
Precisely: the same result without recursion
zipWith (-) (drop 1 week) week gives the same changes. zipWith combines two lists element by element with a function, and drop 1 week is week without its first element. Both forms are correct; choose the one that the people who read your code find clearer.
06 / In production
What goes wrong with repetition in real programs?
Four mistakes with repetition are common in real Haskell code.
A running total that waits. foldl (+) 0, and a helper whose accumulator nothing needs until the end, build one waiting addition per element, as days did in the first experiment. On a long list this uses a lot of memory. Use foldl', the strict left fold from Recursion, or make a guard need the accumulator at each step.
No equation for the empty list. A function written for [present] and (present : rest) works until a week has no school days. Then it stops with Non-exhaustive patterns. GHC’s -Wincomplete-patterns, part of -Wall, warns about this at compile time.
Results thrown away. forM runs an action for each element and gives the list of results; forM_ and mapM_ keep none. mapM_ checkPupil pupils, where checkPupil gives an IO action with a Bool result, runs every check and loses every answer, and -Wall does not warn. Use forM or mapM and look at the results.
A list walked twice. A helper over positions that tests i < length week and reads week !! i walks the list on every step: length counts every cell, and !! walks from the first cell to position i. For n elements that is about n × n steps. Match (present : rest) instead, or use zip [0 ..].
fewest :: [Int] -> Int
fewest [present] = present
fewest (present : rest) = min present (fewest rest)
-- fewest [] stops with Non-exhaustive patternsMake running totals strict, give every list function an answer for [], keep the results you need, and walk a list once.
Experiment
Give a function a list it has no equation for
[present] matches a list of exactly one element, and (present : rest) matches a list of one or more. Neither matches [], so fewest [] has no equation. GHC accepts the patterns, and the program fails only when fewest [] is needed.
Why it matters For every function on lists, decide what it gives for []. When there is no sensible answer, give back a Maybe, or check for [] before the function is used.
Predict what is printed. Then change [26, 24, 27] on line 6 to [], a week with no school days, and predict again.
fewest :: [Int] -> Int
fewest [present] = present
fewest (present : rest) = min present (fewest rest)
main :: IO ()
main = print (fewest [26, 24, 27])
What to look for
The stepper stops twice on line 3 for each day except the last: with present 26 and rest = [24,27], then with present 24 and rest = [27]. The last stop is on line 2 with present 27, the one-element equation. The run prints 24. After the edit, the program still compiles. After two stops on line 6, the run stops with *** Exception: Main.hs:(2,1)-(3,51): Non-exhaustive patterns in function fewest. Nothing is printed.
Expected output
2407 / Try it
Can you predict what each repetition gives?
Decide where each repetition stops, and which list each one sees.
import Data.List (foldl')
main :: IO ()
main = do
let late = [1, 0, 3, 2] :: [Int]
before = takeWhile (< 3) late
total = foldl' (+) 0 late
mapM_ print (zip [1 ..] before)
print total
The list holds the pupils who arrived late on each of four days. What does the program print?
Reveal the reasoning
(1,1), then (2,0), then 6. takeWhile (< 3) stops at 3, the first element that fails the test, so before is [1,0]; the 2 after it is never taken, although 2 < 3. zip [1 ..] before pairs each day with its position, and stops when before ends, so mapM_ print prints two pairs. total folds the whole list, 1 + 0 + 3 + 2, which is 6.
Practice tickets
- HS-401 · Every class reaches its trip goal on day 1 → Free
- HS-402 · Pupils keep scoring after their first spelling mistake → Sign in · Pro
- HS-403 · The longest-lesson screen stops on every school day → Sign in · Pro