PE Problem #2 in All Languages (Part II)

In my last post, I described the top-level function for adding up even Fibonacci numbers less than or equal to 4 million. The real kernel of the problem, though, is to compute Fibonacci numbers.

Naively, Fibonacci numbers are computed with an exponential algorithm. I had thought about writing this version because I suspect that even up to 4 million it wouldn't take that long (although in hindsight I'm less sure). Regardless, the challenge of writing a list-generating version sounded more interesting. (I've written the recursive, exponential algorithm too many times to count, so by definition it's not interesting.)

Haskell

How awesome is Haskell?

Don't worry. It's a rhetorical question. I already know that it "blinds you from over-exposure to pure awesomeness" (to paraphrase Po of Kung Fu Panda).

fibList = 1 : 2 : zipWith (+) fibList (tail fibList)

The : operator builds up a list; zipWith applies + to the two lists passed to it. Of course, if you look closely, those two lists are the same list being defined! This works because of Haskell's lazy evaluation. Not even the : operations execute until some other computation actually needs them. So by the time the zipWith is triggered, the first two elements of fibList exist.

To understand the zipWith, let's pretend that fibList is built up this far: [1, 2, 3, 5, 8, 13] (plus a commitment to build more which we'll ignore for now). So the zipWith expression turns into (by substitution):

zipWith (+) [1, 2, 3, 5, 8, 13] [2, 3, 5, 8, 13]

This applies + to each pair of elements from the two lists which results in: [3, 5, 8, 13, 21]. That's how the rest of the Fibonacci numbers are computed—including the elements in that expression!

This does beg the question: what triggers the computation of fibList? Answer: whatever the top-level output routine wants. The main routine (or the tests) request a particular fibSum; the fibSum computation requests Fibonacci numbers from fibList using this function:

takeFibs n = takeWhile (<=n) fibList

This function will only unravel fibList until the limit is reached.

Erlang

For the other languages, I combined the "take" and the "Fibonacci numbers" computations. Take a look at this:

takeFibs(N) ->
 if
   N == 0 -> [];
   true   -> takeFibs(N, 2, 1, [])
    end.

takeFibs(N, First, Second, Fibs) ->
 if
  First > N -> [Second | Fibs];
  true      -> takeFibs(N,
                               First + Second, First,
                               [Second | Fibs])
 end.

There are two versions of takeFibs (completely different functions because they have different numbers of parameters). The first version is to kick off the computation and deals with the low-limit base cases. The second version does the recursion. It uses an accumulator-passing approach to accumulate a list of Fibonacci numbers. The last two Fibonacci numbers computed are passed in First and Second to make it easier to recognize the base case and to compute the next number in the sequence.

There's something about this approach that doesn't quite satisfy me.

Prolog

How does this strike you?

takeFibs(N, L) :-
 N =:= 0 -> L = [];
 N > 0   -> takeFibs(N, 2, 1, [], L).

takeFibs(N, First, Second, Incoming, Outgoing) :-
 First > N  -> Outgoing = [Second | Incoming];
 First =< N -> Next is First+Second,
   takeFibs(N, Next, First, [Second | Incoming], Outgoing).

It's the same approach as with Erlang. Taking a play from the Erlang playbook, I like how the multiple cases work out this time. Since I'm using ->, unproductive paths through the logic are cut off so no checkpoints are left behind.

Ruby

class Integer
  def fibs_upto
    if zero?
      []
    else
      fibs_upto_helper(2, 1, [])
    end
  end

  private
  def fibs_upto_helper(first, second, fibs)
    if first > self
      [second] + fibs
    else
      fibs_upto_helper(first + second, first, [second] + fibs)
    end
  end
end

Same approach as the others. It seems less slick in Ruby.

Python

def fibs_upto(n):
    if n == 0:
        return []
    else:
        return fibs_upto_helper(n, 2, 1, [])

def fibs_upto_helper(n, first, second, fibs):
    if first > n:
        return [second] + fibs
    else:
        return fibs_upto_helper(n, first + second, first, [second] + fibs)

Same song, same verse. About as icky as the Ruby solution.

Options

As I've read up more about Fibonacci numbers, I suspect that a matrix approach might be a little more satisfying. The non-Haskell solutions could be improved if I used infinite-list solutions in those languages, and that would actually be really interesting to work out.

At this point, though, I'm willing to let this problem go since I do have it solved, and my solutions aren't bad.