Lucid Glitch

Fibo

In a study group discussing Domain-Driven Design (DDD), someone jokingly remarked that DDD doesn’t suit functional programming, saying something along the lines of: “Because in FP you use a language where you implement the Fibonacci sequence using recursion.” It might have been another typical calculation used to introduce FP concepts. I can’t recall exactly.

Anyway, here’s an example of calculating Fibonacci in Clojure:

(defn fib []
  ((fn fibo [a b]
       (cons a (lazy-seq (fibo b (+ a b)))))
    0 1))

I don’t expect everyone in the study group to follow half of what I’m saying here, but for those interested:

This example goes straight to the point, using explicit recursion. It’s elegant and compact, but takes a recursive mindset to follow. We clearly express that the sequence is lazy, which matters since Fibonacci extends infinitely and the caller may only want part of it. Being lazy means values are computed only when needed.

We can take the first 50 values using take, which means only those will be computed.

(take 50 (fib))

Here’s a version I find more aesthetically pleasing. It still generates the sequence lazily but uses functions like map and iterate, which many FP developers are familiar with:

(defn fib []
  (let [fibo (fn [[a b]]
               [b (+ a b)])]
    (map first (iterate fibo [0 1]))))

Again, we can take 50 lazy values from it the same way:

(take 50 (fib))

Haskell is fun when it comes to Fibonacci. It’s often used to explore deeper FP thinking. Haskell is lazy by nature, lazy evaluation, so arguments to functions aren’t evaluated until needed. This naive Fibonacci implementation in Haskell looks just like the mathematical definition:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

And we can get the first 50 numbers using:

take 50 (map fib [0..])

This is naturally lazy and general since we define the range starting from index 0. Elegant. But this version recalculates values repeatedly, which is fine mathematically, but computationally expensive. It slows down quickly. This optimized version avoids that but isn’t as aesthetically pleasing (unless you’re a devoted Haskeller):

fib n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

take 50 (map fib [0..])

In C#, it’s also easy to implement Fibonacci lazily, even without lambdas:

IEnumerable<ulong> fibo()
{
  ulong a = 0, b = 1, c;
  yield return a;
  yield return b;
          
  while (true)
  {
    c = a + b;
    a = b;
    b = c;
    yield return c;
  }
}

While not purely functional, this approach works. C# doesn’t however automatically promote primitive types to arbitrary-precision like most FP languages do. The ulong overflows silently. Still, we can take the first 50 generated values, before the overflow occurs.

Enumerable.Take(fibo(), 50);

You could surely improve this C# code. I don’t have many years of experience in C#.

Then we have Java. Calculating Fibonacci in Java is straightforward, but doing it lazily with only the JDK is verbose due to lack of built-in laziness. We can use an iterator to emit values lazily:

class Fib implements Iterator<Long>, Iterable<Long> {
  long a = 0, b = 1, c = 0;
  int count = 0;

  @Override
  public Long next() {
    count++;
    if (count == 1)
      return a;
    else if (count == 2)
      return b;
    else {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }

  @Override
  public boolean hasNext() {
    return true;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }

  @Override
  public Iterator<Long> iterator() {
    return new Fib();
  }
}

Java doesn’t provide a built-in take function. But we can write an iterator that breaks after 50 elements from another iterator, still lazily.

static <T> Iterable<T> take(final int num, final Iterable<T> iterable) {
    return new Iterable<T>() {

      @Override
      public Iterator<T> iterator() {
        return new Iterator<T>() {
          int i = 0;
          Iterator<T> it = iterable.iterator();

          @Override
          public boolean hasNext() {
            return it.hasNext() && i < num;
          }

          @Override
          public T next() {
            if (hasNext()) {
              i++;
              return it.next();
            }
            throw new NoSuchElementException();
          }

          @Override
          public void remove() {
            throw new UnsupportedOperationException();
          }
        };
      }
    };
  }

Finally:

take(50, new Fib())

Nothing wrong with Java, but the JDK lacks general composable functions, which I noted more than once in my Java 7 talk. Hopefully closures in Java 8 help.