Haskell Basics of Recursion

Let's look at how one might construct two of these.

zip

We'll start with zip. The purpose of zip is to "zip" two lists into one. The name comes from the analogy of zipping two sides of a zipper together. Here's an example of how it functions:

zip [1,2,3] ["a", "b", "c"]
  = [(1,"a"), (2,"b"), (3,"c")]

The type signature of zip (which is typically the first thing you'd write) is

zip :: [a] -> [b] -> [(a, b)]

That is, it takes a list of elements of type a and a list of elements of type b and produces a list of pairs with one component of each type.

To construct this function, let's go for standard Haskell pattern matching. We have four cases:

1. The first list is [] and the second list is [].
2. The first list is [] and the second list is a cons (constructed using :).
3. The first list is a cons and the second list is [].
4. The first list is a cons and the second list is also a cons.

Let's work out each of these.

zip [] [] = ?

If you zip together two empty lists, you have no elements to work with, so surely you get the empty list.

zip [] [] = []

In the next case, we have

zip [] (y : ys) = ?

We have an element, y, of type b, but no element of type a to pair it with. So we can only construct the empty list.

zip [] (y : ys) = []

The same happens in the other asymmetrical case:

zip (x : xs) [] = []

Now we get to the interesting case of two conses:

zip (x : xs) (y : ys) = ?

We have elements of the right types, so we can make a pair, (x, y), of type (a, b). That's the head of the result. What's the tail of the result? Well, that's the result of zipping the two tails together.

zip (x : xs) (y : ys) = (x, y) : zip xs ys

Putting all these together, we get

zip [] [] = []
zip [] (y : ys) = []
zip (x : xs) [] = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

But the implementation you gave only has three cases! How's that? Look at what the first two cases have in common: the first list is empty. You can see that whenever the first list is empty, the result is empty. So you can combine these cases:

zip [] _ = []
zip (x : xs) [] = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

Now look at what's now the second case. We already know that the first list is a cons (because otherwise we'd have taken the first case), and we don't need to know anything more about its composition, so we can replace it with a wildcard:

zip [] _ = []
zip _ [] = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

That's produces the zip implementation you copied. Now it turns out that there's a different way to combine the patterns that I think explains itself a bit more clearly. Reorder the four patterns like this:

zip (x : xs) (y : ys) = (x, y) : zip xs ys
zip [] [] = []
zip [] (y : ys) = []
zip (x : xs) [] = []

Now you can see that the first pattern produces a cons and all the rest produce empty lists. So you can collapse all three of the rest, producing the nicely compact

zip (x : xs) (y : ys) = (x, y) : zip xs ys
zip _ _ = []

This explains what happens when both lists are conses, and what happens when that's not the case.

length

The naive way to implement length is very direct:

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

This will give you correct answers, but it's inefficient. When evaluating the recursive call, the implementation needs to keep track of the fact that once it's done, it needs to add 1 to the result. In practice, it likely pushes the 1+ onto some sort of stack, makes the recursive call, pops the stack, and performs the addition. If the list has length n, the stack will reach size n. That's not great for efficiency. The solution, which the code you copied obscures somewhat, is to write a more general function instead.

-- | A number plus the length of a list
--
-- > lengthPlus n xs = n + length xs
lengthPlus :: Int -> [a] -> Int
-- n plus the length of an empty list
-- is n.
lengthPlus n [] = n
lengthPlus n (_ : xs) = ?

Well,

 lengthPlus n (x : xs)
 = -- the defining property of `lengthPlus`
 n + length (x : xs)
 = -- the naive definition of length
 n + (1 + length xs)
 = -- the associative law of addition
 (n + 1) + length xs
 = -- the defining property of lengthPlus, applied recursively
 lengthPlus (n + 1) xs

So we get

lengthPlus n [] = n
lengthPlus n (_ : xs) = lengthPlus (n + 1) xs

Now the implementation can increment the counter argument on each recursive call instead of delaying them till afterwards. Well ... pretty much.

Thanks to Haskell's call-by-need semantics, this isn't guaranteed to run in constant memory. Suppose we call

lengthPlus 0 ["a","b"]

This reduces to the second case:

lengthPlus (0 + 1) ["b"]

But we haven't actually demanded the value of the sum. So the implementation could defer that addition work, creating a chain of deferrals that's just as bad as the stack seen earlier! In practice, the compiler is clever enough that it will work out how to do this right when optimizations are enabled. But if you don't want to rely on that, you can give it a hint:

lengthPlus n [] = n
lengthPlus n (_ : xs) = n `seq` lengthPlus (n + 1) xs

This tells the compiler that the integer argument actually has to be evaluated. As long as the compiler isn't being intentionally obtuse, it will be sure to evaluate it first, clearing up any deferred additions.

I'm not sure exactly which part you're confused by. Perhaps you're just overthinking this? Let's walk through zip slowly.

For arguments' sake, let's say we want to execute zip [1, 2, 3] ['A', 'B', 'C']. What do we do?

• We have zip [1, 2, 3] ['A', 'B', 'C']. What now?

• The first line ("equation") of the definition of zip says

  zip [] _ = []
  

Is our first argument an empty list? No, it's [1, 2, 3]. OK, so skip this equation.

• The second equation of zip says

  zip _ [] = []
  

Is our second argument an empty list? No, it's ['A', 'B', 'C']. So ignore this equation too.

• The last equation says

  zip (x:xs) (y:ys) = (x, y) : zip xs ys
  

Is our first argument a non-empty list? Yes! It's [1, 2, 3]. So the first element becomes x, and the rest become xs: x = 1, xs = [2, 3].

Is our second argument a non-empty list? Again, yes: y = 'A', ys = ['B', 'C'].

OK, what do we do now? Well, what the right-hand size says. If I put in some extra brackets, the right-hand side basically says

(x, y) : (zip xs ys)

So we're constructing a new list, which starts with (x, y) (a 2-tuple) and continues with whatever zip xs ys is. So our output is (1, 'A') : ???.

What is the ??? part? Well, it's like we executed zip [2, 3] ['B', 'C']. Go back to the top, walk through again the same way as before. You'll find that this outputs (2, 'B') : ???.

Now we started with (1, 'A') : ???. If we replace that with the thing we just got, we now have (1, 'A') : (2, 'B') : ???.

Take this one step further and we have (1, 'A') : (2, 'B') : (3, 'C') : ???. Here the ??? part is now zip [] []. It should be clear that the first equation says this is [], so our final result is

(1, 'A') : (2, 'B') : (3, 'C') : []

which can also be written as

[(1, 'A'), (2, 'B'), (3, 'C')]

You probably already knew that was what the answer would eventually be. I hope now you can see how we get that answer.

If you understand what the three equations make zip do at each step, we can summarise the process like this:

zip [1, 2, 3] ['A', 'B', 'C']
(1, 'A') : (zip [2, 3] ['B', 'C'])
(1, 'A') : (2, 'B') : (zip [3] ['C'])
(1, 'A') : (2, 'B') : (3, 'C') : (zip [] [])
(1, 'A') : (2, 'B') : (3, 'C') : []

If you're still confused, try to put your finger on exactly what part confuses you. (Yeah, easier said than done...)

The key to recursion is to stop worrying about how your language provides support for recursion. You really only need to know three things, which I'll demonstrate using zip as the example.

1. How to solve the base case

   The base case is zipping two lists when one is empty. In this case, we simply return an empty list.

    zip _ [] = []
    zip [] _ = []
   

2. How to break a problem into one (or more) simpler problem(s).

   A non-empty list can be split into two parts, a head and a tail. The head is a single element; the tail is a (sub)list. To zip together two lists, we "zip" together the two heads using (,), and we zip together the two tails. Since the tails are both lists, we already have a way to zip them together: use zip!

   (As a former professor of mine would say, "Trust your recursion".)

   You might object that we can't call zip because we haven't finished defining it yet. But we aren't calling it yet; we are just saying that at some point in the future, when we call this function, the name zip will be bound to a function that zips two lists together, so we'll use that.

      zip (x:xs) (y:ys) = let h = (x,y)
                              t = zip xs ys
                          in ...
   

3. How to put the pieces back together.

   zip needs to return a list, and we have our head h and tail t of the new list. To put them together, just use (:):

       zip (x:xs) (y:ys) = let h = (x,y)
                               t = zip xs ys
                           in h : t
   

   Or more simply, zip (x:xs) (y:ys) = (x,y) : zip xs ys

When explaining recursion, it's usually simplest to start with the base case. However, the Haskell code is sometimes simpler if you can write the recursive case first, because it lets us simply the base case.

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []  -- If the first pattern match failed, at least one input is empty

Taking a step further back, let's introduce the only recursive function you'll ever need:

fix :: (a -> a) -> a
fix f = f (fix f)

fix computes the fixed point of its argument. The fixed point of a function is the value that, when you apply the function, you get back the fixed point. For instance, the fixed point of the square function square x = x**2 is 1, since square 1 == 1*1 == 1.

fix doesn't look terribly useful, though, since it looks like it just gets stuck in an infinite loop:

fix f = f (fix f) = f (f (fix f)) = f (f (f (fix f))) = ...

However, as we'll see, laziness lets us take advantage of this infinite stream of calls to f.

Ok, how do we actually make use of fix? Consider this nonrecursive version of zip:

zip' :: ([a] -> [b] -> [(a,b)]) -> [a] -> [b] -> [(a,b)]
zip' f (x:xs) (y:ys) = (x,y) : f xs ys
zip' _ _ _ = []

Given two nonempty lists, zip' zips them together by using the help function f that it receives to zip the tails of its inputs. If either input list is empty, it ignores f and returns an empty list. Basically, we've left the hard work to whoever calls zip'. We'll trust them to provide an appropriate f.

But how do we call zip'? What argument can we pass? This is where fix comes in. Look at the type of zip' again, but this time make the substitution t ~ [a] -> [b] -> [(a,b)]:

zip' :: ([a] -> [b] -> [(a,b)]) -> [a] -> [b] -> [(a,b)]
     ::           t             ->          t

Hey, that's the type fix expects! What's the type of fix zip'?

> :t fix zip'
fix zip' :: [a] -> [b] -> [(a, b)]

As expected. So what happens if we pass zip' its own fixed point? We should get back... the fixed point, that is, fix zip' and zip' (fix zip') should be the same function. We still don't really know what the fixed point of zip' is, but just for kicks, what happens if we try to call it?

> (fix zip') [1,2] ['a','b']
[(1,'a'),(2,'b')]

It sure looks like we just found a definition of zip! But how? Let's use equational reasoning to figure out what just happened.

(fix zip') [1,2] ['a','b']
  == (zip' (fix zip')) [1,2] ['a','b']  -- def'n of fix
  == (1,'a') : (fix zip') [2] ['b']     -- def'n of zip'
  == (1,'a') : (zip' (fix zip')) [2] ['b'] -- def'n of fix, but in the other direction
  == (1,'a') : ((2,'b') : (fix zip') [] []) -- def'n of zip'
  == (1,'a') : ((2,'b') : zip' (fix zip') [] []) -- def'n of fix
  == (1,'a') : ((2,'b') : [])  -- def'n of zip'

Because Haskell is lazy, the last call to zip' doesn't need to evaluate fix zip', because its value is never used. So fix f doesn't need to terminate; it just needs to provide another call to f on demand.

And in then end, we see that our recursive function zip is simply the fixed point of the nonrecursive function zip':

fix f = f (fix f)
zip' f (x:xs) (y:ys) = (x,y) : f xs ys
zip' _ _ _ = []
zip = fix zip'

Let's briefly use fix to define length and (!!) as well.

length xs = fix go' 0 xs
  where go' _ acc []     = acc
        go' f acc (_:xs) = f (acc + 1) xs

xs !! n = fix (!!!) xs n
  where (!!!) _ [] _ = error "Too big"
        (!!!) _ (x:_) 0 = x
        (!!!) f (x:xs) n = f xs (n-1)

And in general, a recursive function is just the fixed point of a suitable nonrecursive function. Note that not all functions have a fixed point, though. Consider

incr x = x + 1

If you try to call its fixed point, you get

(fix incr) 1 = (incr (fix incr)) 1
             = (incr (incr (fix incr))) 1
             = ...

Since incr always needs its first argument, the attempt to calculate its fixed point always diverges. It should be obvious that incr has no fixed point, because there is no number x for which x == x + 1.

Here’s a nice trick to show how to convert normal imperative loops into recursion. Here are the steps:

1. Make data immutable by not mutating objects (e.g. no x.y = z, only x = x { y = z })
2. Make variables “nearly immutable” by moving all variable-changes to just before control flow
3. Change into “goto form”
4. Work out the set of mutating variables
5. Add “variable changes” for mutating variables that don’t change at each goto
6. Replace labels with functions and goto with function (tail) calls

Here is a simple example after step 1 but before anything else (made up syntax)

let sumOfList f list =
  total = 0
  done = False
  while (not done) {
    case list of
    [] -> done = True
    (x : xs) -> 
      list = xs
      total = total + (f x)
  }
  total

Well this doesn’t really do much other than change variables but there’s one thing we can do for step 2:

let sumOfList f list =
  total = 0
  done = False
  while (not done) {
    case list of
    [] -> done = True
    (x : xs) -> 
      let y = f x in
      list = xs
      total = total + y
  }
  total

Step 3:

let sumOfList f list =
  total = 0
  done = False
  loop:
    if not done then goto body else goto finish
  body:
    case list of
    [] -> 
      done = True
      goto loop
    (x : xs) -> 
      let y = f x in
      list = xs
      total = total + y
      goto loop
  finish:
    total

Step 4: the mutating variables are done, list, and total

Step 5:

let sumOfList f list =
  done = False
  list = list
  total = 0
  goto loop
  loop:
    if not done then 
      total = total
      done = done
      list = list
      goto body
    else
      total = total
      done = done
      list = list
      goto finish
  body:
    case list of
    [] -> 
      done = True
      total = total
      list = list
      goto loop
    (x : xs) -> 
      let y = f x in
      done = done 
      total = total + y
      list = xs
      goto loop
  finish:
    total

Step 6:

let sumOfList f list = loop False list 0 where
  loop done list total =
    if not done
    then body done list total
    else finish done list total
 body done list total =
   case list of
   [] -> loop True list total
   (x : xs) -> let y = f x in loop done list (total + y)
 finish done list total = total

We can now clean things up by removing some unused parameters:

let sumOfList f list = loop False list 0 where
  loop done list total =
    if not done
    then body done list total
    else finish total
 body done list total =
   case list of
   [] -> loop True list total
   (x : xs) -> let y = f x in loop done list (total + y)
 finish total = total

And realising that in body done is always False and inlining loop and finish

let sumOfList f list = body list 0 where
 body list total =
   case list of
   [] -> total
   (x : xs) -> let y = f x in body list (total + y)

And now we can pull the case into multiple function definitions:

let sumOfList f list = body list 0 where
 body [] total = total
 body (x : xs) total =
   let y = f x in body list (total + y)

Now inline the definition of y and give body a better name:

let sumOfList f list = go list 0 where
 go [] total = total
 go (x : xs) total = go list (total + f y)

A loop is a function call is a loop. Reentering a loop body with updated loop parameters is the same as reentering a function body in a new recursive call with the updated function parameters. Or in other words, a function call is a goto, and the function name is the label to jump to:

    loop_label: 
         do stuff updating a, b, c,
         go loop_label

is

    loop a b c = 
        let a2 = {- .... a ... b ... c ... -}
            b2 = {- .... a ... b ... c ... -}
            c2 = {- .... a ... b ... c ... -}
        in
           loop a2 b2 c2

You did say you're comfortable with loops.

Let's give the translations of your example functions in terms of the more primitive construct, case, as defined in the Report:

length xs = go 0 xs
    where
    go a b = case (a , b) of
               ( acc , []       )   ->      acc
               ( acc , (_ : xs) )   ->  go (acc + 1) xs

so it's the same old plain linear recursion.

Same goes to the other two definitions:

zip a b = case ( a  , b  ) of
            (  []   , _     )  ->  []
            (  _    , []    )  ->  []
            (x : xs , y : ys)  ->  (x,y) : zip xs ys

(the last one is left as an exercise).