Recursion with Haskell

Question

I am struggling to understand the logic of the code below. I know the code will return a list of Fibonacci numbers from the first till nth e.g. fib 3 will produce [2,1,1,0]. I do not understand how 'n' is split up in (x:y:xs).

I would appreciate any light on this.

Thanks

fib 1 = [1, 0]
fib n = x + y : (x:y:xs)
    where (x:y:xs) = fib (n-1)

Answer 1

I do not understand how n is split up in (x:y:xs).

n is not being split; the list resulting from fib is being split.

The original code:

fib 1 = [1, 0]
fib n = x + y : (x:y:xs)
    where (x:y:xs) = fib (n-1)

Is equivalent to the following, with some of the syntactic sugar removed:

fib n =
  if n == 1
    then [1, 0]
    else case fib (n - 1) of
      x : (y : xs) -> (x + y) : (x : (y : xs))
      _ -> error "pattern match failure"

Since this code just destructures the list and then rebuilds an identical one, the case branch can also be written using an “as” pattern, e.g.: res@(x : y : xs) -> (x + y) : res

So fib is a function which takes one parameter n, which may be of any numeric type. In the base case when n is 1, the code just returns a constant list [1, 0]. In the recursive case, fib calls itself recursively, replacing n with n - 1. The result will be a list, so the function then pattern-matches on that list to extract its components.

In the pattern x : y : xs, which is syntactic sugar for (:) x ((:) y xs), the operator (:) :: a -> [a] -> [a] is the data constructor for a list that is not empty, and x, y, and xs are variables; so this is equivalent to saying “if the input (the result of fib (n - 1)) is non-empty, then name its head x; and if its tail is non-empty, then name the head and tail of that y and xs respectively”. In other words, if it’s a list of at least two elements, then call the first element x, the second y, and the remainder xs (which may be empty).

In fact it can be implemented in that explicit way, as you’d do in a language that lacks pattern-matching, by using guards or if expressions. The result is quite unwieldy and error-prone, but it may be helpful as an illustration of how to mentally break it down:

fib n

  | n == 1
    = [1, 0]

  | let temp1 = fib (n - 1)
  , not (null temp1)
  , let x = head temp1
  , let temp2 = tail temp1
  , not (null temp2)
  , let y = head temp2
  , let xs = tail temp2
    = x + y : temp1

  | otherwise
    = error "pattern match failure"

fib n =
  if n == 1
    then [1, 0]
    else let
      temp1 = fib (n - 1)
    in if not (null temp1)
      then let
          x = head temp1
          temp2 = tail temp1
        in if not (null temp2)
          then let
              y = head temp2
              xs = tail temp2
            in x + y : temp1
          else error "pattern match failure"
      else error "pattern match failure"

Obviously pattern matching is much simpler!

So here’s an example of how the original code would evaluate on the example input you gave, fib 3:

• evaluate: fib 3
  • matches equation #2 with n₀ = 3: let (x₀ : y₀ : xs₀) = fib (3 - 1) in x₀ + y₀ : (x₀ : y₀ : xs₀)
  • evaluate: fib 2
    • matches equation #2 with n₁ = 2: let (x₁ : y₁ : xs₁) = fib (2 - 1) in x₁ + y₁ : (x₁ : y₁ : xs₁)
    • evaluate: fib 1
      • matches equation #1: [1, 0]
    • substitute: let (x₁ : y₁ : xs₁) = 1 : 0 : [] in x₁ + y₁ : (x₁ : y₁ : xs₁)
    • evaluate let with x₁ = 1, y₁ = 0, xs₁ = []: 1 + 0 : (1 : 0 : [])
  • substitute: let (x₀ : y₀ : xs₀) = 1 : 1 : [0] in x₀ + y₀ : (x₀ : y₀ : xs₀)
  • evaluate let with x₀ = 1, y₀ = 1, xs₀ = [0]: 1 + 1 : (1 : 1 : [0])
• syntactic sugar for lists: [2, 1, 1, 0]

And a diagram, showing how it builds up a list where each element’s value refers to the subsequent two elements:

          ┌─────┬───────────┬───────┐ ┌─────┬───────────┬───────────┐ ┌─────┬───┬─────┐ ┌─────┬───┬───┐ ┌────┐
… fib 3───▶ (:) │ (+) x₁ y₁ │ fib 2─┼─▶ (:) │ (+) x₀ y₀ │ xs₁/fib 1─┼─▶ (:) │ 1 │ xs₀─┼─▶ (:) │ 0 │ ○─┼─▶ [] │
          └─────┴─────┼──┼──┴───────┘ └─────┴──▲──┼──┼──┴───────────┘ └─────┴─▲─┴─────┘ └─────┴─▲─┴───┘ └────┘
                      └──┼─────────────────────┘  │  └────────────────────────┼─────────────────┘
                         └────────────────────────┴───────────────────────────┘

ASCII version:

          +-----+-----------+-------+   +-----+-----------+-----------+   +-----+---+-----+   +-----+---+---+   +----+
          |     |           |       |   |     |           |           |   |     |   |     |   |     |   |   |   |    |
… fib 3---> (:) | (+) x1 y1 | fib 2-+---> (:) | (+) x0 y0 | xs1/fib 1-+---> (:) | 1 | xs0-+---> (:) | 0 | o-+---> [] |
          |     |     |  |  |       |   |     |     |  |  |           |   |     |   |     |   |     |   |   |   |    |
          +-----+-----+--+--+-------+   +-----+--^--+--+--+-----------+   +-----+-^-+-----+   +-----+-^-+---+   +----+
                      |  |                       |  |  |                          |                   |
                      +--+-----------------------+  |  +--------------------------+-------------------+
                         |                          |                             |
                         +--------------------------+-----------------------------+

Notice the calls to error: if you try to evaluate a pattern match that isn’t exhaustive, it will throw an exception. In this case, fib will always have at least two elements, so the let binding is safe, but consider how you could change the structure of the code to avoid needing this partial match.

Answer 2

Your comment about "how" the code splits up the list returned by fib I cannot answer as I don't know all the internals of GHC. This process is called patter matching. In Python and other languages you may be familiar with, this can be done

a, b = (1,2)
# a == 1
# b == 2

Your function is of type

fib :: Int -> [Int]

so you can use pattern matching to extract the head, next head, and next tail of the list it returns, which is what happens in

where (x:y:xs) = fib (n-1)

Perhaps an area of confusion is where the list is being reconstructed so it can be appended to the rest of the list you are returning. Your function can also be written like this

fib 1 = [1, 0]
fib n = x + y : (fib (n-1))
    where (x:y:xs) = fib (n-1)