Polyglot
› Languages › Haskell › loops
Haskell § loops

Recursion

Haskell does not have for, while, do … while, or any other loop construct. The mechanism for iteration is recursion — direct recursion when the structure of the input dictates the recursion shape, or higher-order functions (map, foldr, replicate, iterate, mapM_) when the iteration follows a conventional pattern. The combination admits expressing every loop in idiomatic Haskell, often more concisely than the C-family forms; the discipline is to recognise which form is appropriate for each situation.

This page covers direct recursion, the principal recursion patterns, the higher-order functions that subsume most loops, and the conventions for using each.

Direct recursion

A recursive function calls itself, typically on a smaller version of its input:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

length :: [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

The pattern: a base case (no recursion) and one or more recursive cases (call on a smaller input). The recursion terminates when the base case is reached.

Direct recursion is the principal iteration mechanism in Haskell. The compiler admits it natively, the language has no syntactic overhead for it, and most non-trivial functions are recursive in some form.

Pattern matching and recursion

Recursive functions conventionally pattern-match on their argument:

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter _ []     = []
filter p (x:xs)
    | p x       = x : filter p xs
    | otherwise = filter p xs

The pattern of “case-split on the structure, recurse on the smaller piece” is the conventional Haskell idiom for list processing.

Tail recursion

A tail-recursive function’s recursive call is the last operation in the function:

-- Not tail-recursive (the `n *` happens after the recursive call):
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- Tail-recursive:
factorial :: Int -> Int
factorial = go 1
  where
    go !acc 0 = acc
    go !acc n = go (acc * n) (n - 1)

The tail-recursive form uses an accumulator — a variable that carries the in-progress result through the recursion. The !acc (with the BangPatterns extension) ensures the accumulator is forced each step, preventing thunk accumulation.

In strict languages, tail recursion matters because tail-call optimisation eliminates stack growth. In Haskell, the situation is more subtle:

  • Lazy evaluation means the recursive call may not actually consume stack until the result is forced.
  • Tail-recursive functions still allocate thunks for the accumulator unless the accumulator is forced (with ! or seq).
  • For numeric folds, foldl' is the conventional strict variant of foldl.

The principal practical guidance:

  • For numeric accumulators, use foldl' from Data.List or write a tail-recursive helper with a strict accumulator.
  • For list-producing functions, write the non-tail-recursive form — Haskell’s lazy evaluation produces the result incrementally:
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

The non-tail-recursive form is the right choice here because the result is consumed lazily; the apparent “stack growth” never materialises.

Mutual recursion

Two or more functions may call each other:

isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n - 1)

isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n - 1)

Mutual recursion is occasionally useful for state-machine-style code or for tree traversals where each level alternates with the next. The compiler handles it natively.

The principal higher-order functions

A substantial fraction of explicit recursion in Haskell code can be replaced by higher-order functions:

map

Apply a function to every element of a list:

map :: (a -> b) -> [a] -> [b]

map (* 2) [1, 2, 3, 4]              -- [2, 4, 6, 8]
map show [1, 2, 3]                  -- ["1", "2", "3"]
map (+ 1) [1..10]                   -- [2, 3, 4, ..., 11]

map is the conventional iteration when the body produces one result per input.

filter

Keep elements satisfying a predicate:

filter :: (a -> Bool) -> [a] -> [a]

filter even [1..10]                 -- [2, 4, 6, 8, 10]
filter (> 5) [1..10]                -- [6, 7, 8, 9, 10]
filter (not . null) ["", "a", "", "b"]  -- ["a", "b"]

foldr and foldl

Reduce a list by applying a binary function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

foldr (+) 0 [1, 2, 3, 4]            -- 10
foldr (\x acc -> x : acc) [] [1, 2, 3]  -- [1, 2, 3]; foldr is "right fold"

foldl (+) 0 [1, 2, 3, 4]            -- 10 (lazy; may produce thunks)
foldl' (+) 0 [1, 2, 3, 4]            -- 10 (strict; preferred)

The principal trade-offs:

  • foldr builds the result from the right; works on infinite lists if the function is lazy in its second argument.
  • foldl builds from the left; does not work on infinite lists and may produce thunks.
  • foldl' is the strict left fold; the conventional choice for numeric accumulators.

The conventional advice:

  • Use foldr when the function naturally produces the result from the right (list-building, lazy operations).
  • Use foldl' for numeric or other strict accumulations.

zip, zipWith

Pair elements of two lists:

zip :: [a] -> [b] -> [(a, b)]
zip [1, 2, 3] ['a', 'b', 'c']       -- [(1,'a'), (2,'b'), (3,'c')]

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (+) [1, 2, 3] [10, 20, 30]  -- [11, 22, 33]

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

zip and zipWith admit iterating over two (or three) parallel lists.

take, drop

Take or drop the first n elements:

take :: Int -> [a] -> [a]
take 3 [1..10]                      -- [1, 2, 3]

drop :: Int -> [a] -> [a]
drop 3 [1..10]                      -- [4, 5, 6, 7, 8, 9, 10]

Both are lazy; take 3 from an infinite list takes the first three.

iterate and replicate

Generate sequences:

iterate :: (a -> a) -> a -> [a]
iterate (* 2) 1                     -- [1, 2, 4, 8, 16, ...]
iterate (+ 1) 0                      -- [0, 1, 2, 3, ...]

replicate :: Int -> a -> [a]
replicate 5 'x'                      -- "xxxxx"
replicate 3 [1, 2]                  -- [[1,2], [1,2], [1,2]]

iterate produces an infinite list; replicate produces a finite list.

repeat and cycle

repeat :: a -> [a]
repeat 'x'                           -- "xxxxxxxxxxx..."

cycle :: [a] -> [a]
cycle [1, 2, 3]                     -- [1, 2, 3, 1, 2, 3, ...]

Both produce infinite lists; conventional in combination with take.

mapM_ and forM_ (for IO)

Iterate effectfully over a list:

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

main = mapM_ print [1, 2, 3, 4, 5]
-- prints each on a new line

main = forM_ [1..10] $ \n -> do
    putStrLn $ "n = " ++ show n

The mapM_ discards the results; mapM collects them:

results <- mapM compute [1..100]    -- collect IO results
forM_ items $ \item ->              -- iterate effectfully, discard
    process item

The treatment is in IO.

List comprehensions

A list comprehension is a compact list-building syntax:

squares :: [Int]
squares = [x * x | x <- [1..10]]
-- [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

evens :: [Int]
evens = [x | x <- [1..20], even x]
-- [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

pairs :: [(Int, Int)]
pairs = [(x, y) | x <- [1..3], y <- [1..3], x /= y]
-- [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

primes :: [Int]
primes = [n | n <- [2..], not (any (\p -> n `mod` p == 0) [2..n-1])]
-- the prime sieve, in one line

The form: [<expression> | <generator>, <generator>, ..., <guard>]. Each generator (x <- xs) iterates over a source; each guard filters; the expression is computed for each combination.

List comprehensions are syntactic sugar for concatMap and filter:

[x * x | x <- xs]  =  map (\x -> x * x) xs
[x | x <- xs, p x]  =  filter p xs
[(x, y) | x <- xs, y <- ys]  =  concatMap (\x -> map (\y -> (x, y)) ys) xs

The conventional contemporary advice is to use list comprehensions for simple cases (filter, map, generate) and to fall back to explicit map/filter for the more complex cases.

The Foldable and Traversable classes

Many higher-order operations work on any Foldable or Traversable type, not just lists:

import Data.Foldable

sum :: (Foldable t, Num a) => t a -> a
length :: Foldable t => t a -> Int
elem :: (Foldable t, Eq a) => a -> t a -> Bool

import Data.Traversable

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

The classes admit applying the conventional list operations to Maybe, Either, Map, Set, Tree, and any user-defined type that admits the right structure. The treatment is in Functors and applicatives and Data structures.

Common iteration patterns

Count something

count :: (a -> Bool) -> [a] -> Int
count p = length . filter p

countMatches = count (> 100) values

Or:

import Data.List (foldl')

count :: (a -> Bool) -> [a] -> Int
count p = foldl' (\acc x -> if p x then acc + 1 else acc) 0

The two forms are equivalent for finite lists; the foldl' version may be marginally faster (one pass instead of two).

Iterating with side effects

import Control.Monad (forM_)

main = forM_ urls $ \url -> do
    response <- fetch url
    saveResponse response

The pattern admits effectful iteration in IO or any other monad.

Iterating with index

import Data.List (zip)

main = mapM_ (\(i, x) -> putStrLn (show i ++ ": " ++ show x))
             (zip [0..] items)

Or:

import Data.List (zip)

processWithIndex :: [a] -> [b]
processWithIndex xs = [process i x | (i, x) <- zip [0..] xs]

The conventional Haskell idiom for “iterate with the position”.

Iterating until condition

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile (< 100) [1..]              -- [1, 2, 3, ..., 99]

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile (< 5) [1..10]              -- [5, 6, 7, 8, 9, 10]

iterate :: (a -> a) -> a -> [a]
takeWhile (< 1000) (iterate (* 2) 1) -- [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

The combination of iterate and takeWhile admits “iterate until the condition” without an explicit loop.

Until convergence

import Data.List (find)

iterate :: (a -> a) -> a -> [a]
converge :: Eq a => (a -> a) -> a -> a
converge f x = case find (uncurry (==)) (zip iter (tail iter)) of
    Just (a, _) -> a
  where
    iter = iterate f x

The pattern admits “iterate until two consecutive values are equal” — the conventional fixed-point construction in functional programming.

A note on “where are my loops”

Programmers coming from C-family languages frequently ask “where are my loops?” The answer:

  • Iteration over a known source: map, filter, mapM_, list comprehension.
  • Reduction: foldr, foldl'.
  • Iteration with state: tail-recursive helper with accumulator, or the State monad.
  • Iteration until condition: iterate + takeWhile/find.
  • Effectful iteration: forM_, mapM_, traverse_.
  • Truly explicit loop: hand-written recursion.

The combination covers every case the C-family loop forms cover, often more concisely. The discipline is to recognise the pattern and use the appropriate higher-order function; the explicit recursion form is a fallback for cases not covered by the conventional toolkit.

The lack of imperative loops is a substantial part of Haskell’s identity. The conventional advice for new Haskell code: try first with the higher-order functions; fall back to explicit recursion only when the higher-order form would be unclear.