FP and C++: A Left Fold Fibonacci Implementation

So today, I was tinkering around with doing functional programming in C++ and thought about implementing one of the traditionally recursively implemented Fibonacci sequence generator. The classic problem is how would you write a function "fib" such that given a parameter "n" it will yield the nth fibonacci number.

The traditional implementation (recursive) would look like this:

unsigned long fib(int n) {
  if (n <= 1uL) return 1uL;
  return fib(n - 2) + fib(n - 1);
}

So that's not particularly surprising nor efficient (space or runtime-wise). So we then think about how we can optimize it. Some people will think about memoization where we'll remember previously computed fibonacci numbers so the next time we compute it we'll benefit form cached values. That's alright because it amortizes the running time as you call the fib function more and more.

If you don't know it yet, there's actually a way to get fibonacci numbers with an linear (O(n)) running time algorithm. It's no fun implementing a loop ourselves, and to show that it's possible in C++, we use the existing numeric algorithm 'accumulate' which behaves precisely as a left fold.

First, we need to implement the function object that will actually perform the binary operation that will yield the accumulated value. The good thing with the binary function object we're going to write is that the left parameter can have a different type from the right parameter. We can then use this to return a 'state' variable that is preserved as the left parameter of the next invocation of the function object.

Let's see the code as we would write it:

struct fibonacci_folder {
  template <class T, class U>
  pair<U,U> operator()(pair<U,U> const & state, T) const {
    return make_pair(state.second, state.first + state.second);
  }
};

So given the above implementation, the first (or left) parameter to the call to the fibonacci_folder function object is a pair which we can call the state object. This state object carries two values which are the 'previous' and 'current' value in the computation being used by the fibonacci fold. The second parameter though is ignored in this computation.

If we can visualize it somehow, we can start with just two numbers (0,1). As we call fibonacci_folder()( (0,1), ignored ), it will return a pair (1, 1). The next call will become then fibonacci_folder()( (1,1), ignored ), and yield (1, 2). You can continue this as long as we're iterating.

Next thing we need to do is setup our boundary iterators. If you notice, accumulate requires that you have forward iterators as the first two arguments giving the bounds upon which the function F(accumulated, *iterator) where F is the function object, accumulated is the state, and iterator is a forward iterator. We can do this simply with a Boost.Iterator called a counting_iterator<T> which simply yields a value of type T. We can then see that we can set up the left fold using accumulate with the fibonacci_folder this way:

unsigned long fib(int n) {
  return accumulate(
    make_counting_iterator(0),
    make_counting_iterator(n),
    make_pair(0uL,1uL),
    fibonacci_folder()
    ).second; // we want the "current" value in the state
}

This now allows us to compute the nth fibonacci number in linear time using a left fold implementation.

Do you know any other interesting algorithms that are effectively converted to and are more efficient as folds instead of recursive or simply loop-based implementations? Do you think writing in this style is more elegant than simply using imperative programming principles?

I'd love to know what you think!