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:

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

  1. Write myTake :: Int -> [a] -> [a] recursively and compare it with the Prelude on a list of five elements and a count of ten.
  2. Write myElem :: Eq a => a -> [a] -> Bool with a base case and a step, then with a guard for the found case.
  3. Write countEven :: [Int] -> Int by recursion and predict its result on [1 .. 10].
  4. Explain why productList has 1 as its base case and what happens if it is 0.
  5. Time myReverse on lists of 1000, 2000 and 4000 elements; the ratios show the quadratic growth.
  6. 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.

  1. 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.

  2. What does sumList [1, 2, 3, 4] return in the lesson program?

    Answer

    10

    The four elements are added: 1 + 2 + 3 + 4 = 10.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. What does myLength ([10, 20, 30] :: [Int]) print?

    Answer

    3

    The function counts the cons cells: one per element, so three.

  9. 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.

  10. Which library functions do the three hand-written recursions reproduce?

    Answer

    sum, product and replicate

    The 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