Recursion replaces loops
The base case
There are no loops in Haskell, and none are needed: a list is a chain, and a recursive function takes one cell off the front and calls itself on the rest until nothing is left. The empty list is the base case, the answer that needs no further call, and it is the first equation of every recursive function over a list.
sumList :: [Int] -> Int
sumList [] = 0
sumList (x : xs) = x + sumList xs
Read the two equations as a definition by cases: the sum of no numbers is zero, and the sum of a list with a first element is that element plus the sum of the rest. There is no index, no counter and no condition to get wrong; the pattern (x : xs) is what a loop condition would be in another language, and the shrinking argument is what the loop variable would be.
The recursive step
The step must make progress: the call is on xs, which is one cell shorter than the list the function received, so after as many calls as there are elements the argument is [] and the base case answers. A recursive call on the same list, or on a longer one, does not terminate, and GHC does not diagnose that: it is a run-time hang, not a type error.
module Main (main) where
sumList :: [Int] -> Int
sumList [] = 0
sumList (x : xs) = x + sumList xs
productList :: [Int] -> Int
productList [] = 1
productList (x : xs) = x * productList xs
replicateN :: Int -> a -> [a]
replicateN 0 _ = []
replicateN n x = x : replicateN (n - 1) x
main :: IO ()
main = do
print (sumList [1, 2, 3, 4])
print (productList [1, 2, 3, 4])
print (replicateN 3 'a')
ghc -Wall -O1 -o sumlist sumlist.hs
./sumlist
10
24
"aaa"
Three recursions with three different bases: zero for a sum, one for a product, the empty list for a list. The product one is worth a second look: the base case is 1, not 0, because 0 would make every product zero. The choice of base case is part of the definition, not a formality.
Three functions by hand
The Prelude already has sum, product and replicate, and writing them once by hand is the fastest way to see what the library does. The shape is always the same:
- one equation for [] with the answer for nothing,
- one equation for (x : xs) that combines x with the result on xs.
The combination is the only part that differs: (+) for a sum, (*) for a product, (:) for a list that keeps the elements. The lesson on folds names that observation: a whole family of functions is one function parameterised by the combination and the base case, and the hand-written versions here are special cases of it.
A reverse you can measure
reverse is the classic example of a recursion whose naive form is quadratic. Written with ++ and a single element, it looks as short as the others and costs far more:
module Main (main) where
myLength :: [a] -> Int
myLength [] = 0
myLength (_ : xs) = 1 + myLength xs
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x : xs) = myReverse xs ++ [x]
main :: IO ()
main = do
print (myLength ([10, 20, 30] :: [Int]))
print (myReverse [1, 2, 3] :: [Int])
print (myReverse "abc" :: String)
ghc -Wall -O1 -o reverse_rec reverse_rec.hs
./reverse_rec
3
[3,2,1]
"cba"
The output is right and the cost is not: each step appends a list of one element to the end of the reversed tail, and append walks its left argument, so the steps cost 1, 2, 3, ... cells and the total is quadratic. The next lesson replaces it with an accumulator, which walks the list once and builds the result with :, and the difference is the reason the accumulator is the standard shape for a loop in Haskell.
The call stack
sumList (x : xs) cannot return before sumList xs does, because the addition needs both numbers. So the calls pile up: one frame per element, and the additions run from the end of the list backwards. A list of ten million elements therefore needs a stack of ten million frames, and the program can die with a stack overflow even though the arithmetic is trivial.
That is what tail recursion fixes, and why the next lesson exists: go (acc + x) xs can return whatever the recursive call returns, so the frame does not have to stay. It is not the whole story in a lazy language, and the next lesson shows the part that is not fixed by the shape of the call.
Exercises
- Write myTake :: Int -> [a] -> [a] recursively and compare it with the Prelude on a list of five elements and a count of ten.
- Write myElem :: Eq a => a -> [a] -> Bool with a base case and a step, then with a guard for the found case.
- Write countEven :: [Int] -> Int by recursion and predict its result on [1 .. 10].
- Explain why productList has 1 as its base case and what happens if it is 0.
- Time myReverse on lists of 1000, 2000 and 4000 elements; the ratios show the quadratic growth.
- Rewrite myLength with an accumulator and say which version keeps the stack small.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the base case of a recursive function over a list?
Answer
The equation for the empty list
Recursion over a list shrinks it until nothing is left, so the empty list is where the recursion stops.
-
What does
sumList [1, 2, 3, 4]return in the lesson program?Answer
10
The four elements are added: 1 + 2 + 3 + 4 = 10.
-
Why is the base case of a product 1 and not 0?
Answer
1 is the identity of multiplication, so the empty product is 1
Multiplying by the base case must leave the other factor unchanged, and only 1 does that.
-
What does this program print?
module Main (main) where replicateN :: Int -> a -> [a] replicateN 0 _ = [] replicateN n x = x : replicateN (n - 1) x main :: IO () main = print (replicateN 3 'a')Answer
"aaa"
Three cons cells of the character a make a String, and print shows a String with quotes.
-
Why is
myReverse (x : xs) = myReverse xs ++ [x]quadratic?Answer
append walks its left argument, which grows at every step
The left argument of ++ is the reversed tail, which grows by one at each step, so the total work is 1 + 2 + ... + n.
-
What makes a recursive call shrink the problem?
Answer
Calling on a subterm, such as the tail of the list
The argument must get smaller, and the tail of a cons cell is one cell shorter than the list.
-
What happens if a recursive function calls itself on the same list?
Answer
It runs forever, because the base case is never reached
There is no shrinking argument and no type error to catch it, so the program hangs or runs out of stack.
-
What does
myLength ([10, 20, 30] :: [Int])print?Answer
3
The function counts the cons cells: one per element, so three.
-
Why does
sumList (x : xs)keep a stack frame per element?Answer
The addition needs the result of the recursive call before it can return
The work after the call, x + ..., depends on the answer, so the frame cannot be discarded early.
-
Which library functions do the three hand-written recursions reproduce?
Answer
sum,productandreplicateThe lesson writes sumList, productList and replicateN, which are the Prelude sum, product and replicate.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev