A Simpler Case for Functional Programming & “Elegant” Code

A lot has been written about the benefits of functional programming, but little of it is accessible to a newcomer. Some of the benefits are easy to understand from an inexperienced perspective (e.g. “it makes concurrency easier”), but others are pretty nebulous.

Chief amongst the inscrutable properties of functional programming is its “elegance.” It isn’t immediately clear what that word actually means in this context. Imperative code is often described as elegant. Really terse, abstruse code is sometimes labeled elegant. Weddings are elegant. It means different things to different people.

What Makes Code Elegant?

Elegant code isn’t always a good thing. Elegance is a superficial, aesthetic property. Finely tuned, optimized, fast code that’s kludgy and awkward might be a marvel of engineering and the only workable solution to a specific problem, but it’s probably not elegant. That’s totally fine.

However, trying to convince a newcomer to study functional programming by showing them a highly optimized example isn’t likely to bear fruit. Understanding a particular optimization probably requires deep knowledge of a language or a domain. It isn’t something you can see.

Elegance, on the other hand, can be seen and pointed out easily, even to someone with no knowledge of a specific language. That’s why, when attempting to express the merits of functional programming to someone who hasn’t been exposed to the concept, it’s useful to appeal to its elegance.

Elegant code might have one or more of the following characteristics:

1. Elegant code is simple (but not necessarily efficient). This means fewer moving parts.
2. Elegant code might be shorter, but only because it doesn’t spend a lot of space on setup and bookkeeping.
3. Elegant code expresses an idea the same way you would express it to another person verbally.

A Simple Example

To use a common example, think of the Fibonacci sequence and how you would explain it to another human being. You would probably say something like:

The Fibonacci sequence is the sequence of numbers that begins with 0 and 1, and every subsequent number is found by adding the two previous numbers.

It’s easy to express this with recursion, which is a hallmark of the functional style, and the code will map directly to the plain English explanation above. (Disclaimer: This code isn’t efficient, but that’s not the point of the example.)

-- The sequence of numbers that begins with 0
fib 0 = 0
-- and 1
fib 1 = 1
-- and every subsequent number is found by adding the two previous numbers
fib n = fib (n - 1) + fib (n - 2)  

Now, compare that with an imperative (and more efficient) implementation in C.

   int n, next, first = 0, second = 1

   for ( int i = 0 ; i < n ; i++ )
   {
      if ( i <= 1 )
         next = i;
      else
      {
         next = first + second;
         first = second;
         second = next;
      }
      printf("%d\n",next);
   }

This looks nothing like our plain English explanation. Here's what that might sound like:

Set first to 0 and second to 1. Then, start counting from zero. Increment twice. Now, the next number is going to be first plus second. Reassign first to equal second and second to equal next. Print out next because that's the next Fibonacci number. Increment the counter, and do it again until your counter is one less than the number of Fibonacci numbers you want to generate.

What a mouthful. Why should we have to reassign first and second? Does the meaning of first and second change throughout this process? No, the first Fibonacci number is always 0, and the second one is always 1.

Maybe there are some names that make more sense. first really means the Fibonacci number that appeared two times ago, and second really means the Fibonacci number that appeared last time.

There are some possibilities that would be more descriptive but are actually painful to write: previous and previousprevious would describe it well. Or, since we're calling our i'th number next, we can say nextminusone and nextminustwo. Bad.

Another problem is that almost this entire code snippet is dedicated to bookkeeping–that is, keeping track of iterators and keeping track of previous values so they're available on the next iteration. The real heart of what it means to be a Fibonacci number exists only on lines 1 and 9. That's two lines out of 14. Not elegant.

A More Complicated Example

Merge sort is the canonical divide-and-conquer algorithm that everyone learns about when they are first exposed to the idea. Let's compare and contrast a functional and an imperative implementation of merge sort. First, the plain English explanation:

To sort a list, first divide the list in half. Recursively sort each half, then combine them. If a list has only one element, then consider it sorted.

Let's look at the imperative implementation first:

void merge(int left[], int leftLength, int right[], int rightLength, int arr[], int length){
    int i = 0;
    int l = 0;
    int r = 0;
    
    while (l < leftLength && r < rightLength) {
        if (left[l] < right[r]) {
            arr[i++] = left[l++];
        } else {
            arr[i++] = right[r++];
        }
    }
    
    for (; l < leftLength; l++) {
        arr[i++] = left[l];
    }
    
    for (; r < rightLength; r++) {
        arr[i++] = right[r];
    }
}

void mergeSort(int arr[], int length) {
    if (length <= 1) {
        return;
    }
    
    int leftLength = length / 2;
    int rightLength = length - leftLength;
    int left[leftLength];
    int right[rightLength];
    int i = 0;
    
    for (int j = 0; j < leftLength; j++) {
        left[j] = arr[i++];
    }
    
    for (int j = 0; j < rightLength; j++) {
        right[j] = arr[i++];
    }

    mergeSort(left, leftLength);
    mergeSort(right, rightLength);
    merge(left, leftLength, right, rightLength, arr, length);
}

Starting in the mergeSort function, we see some code to determine the boundaries of the left and right sub lists, and then some code to copy things out of the source array and into temporary arrays. A lot of necessary bookkeeping before the real fun starts.

The last three lines of the function are where we can start to see the heart of the algorithm. The function recursively calls itself on the left half, the right half, and then merges the result.

It's also worth noting that merge doesn't return a result. It mutates one of its six arguments. In this case, it's easy to figure out which one, but that won't always be the case.

The merge function will make your eyes glaze over immediately with three assignments to index variables (separated onto multiple lines for maximum impact). Then the brain bending iteration begins. l and r track the left and right arrays, and i tracks the final (merged) array. The iteration will end when l and r are strictly less than their length, or is it less than or equal? Don't be off by one.

All of the elements of the plain English explanation are present in this code, but they are buried in tons of noise.

Now, let's look at the Lisp.

(define (mergesort l)
  (define (leftside l)
    (let ((length (floor
                   (/ (length l)
                      2))))
      (take l length)))

  (define (rightside l)
    (let ((length (floor
                   (/ (length l)
                      2))))
      (drop l length)))

  (define (merge left right)
    (cond ((null? left) right)
          ((null? right) left)
          ((or (< (car left) (car right))
               (= (car left) (car right)))
           (cons (car left)
                 (merge (cdr left)
                        right)))
          (else (cons (car right)
                      (merge left
                             (cdr right))))))

  (cond ((null? (cdr l))
         l)
        (else (merge (mergesort (leftside l))
                     (mergesort (rightside l))))))

If you aren't used to looking at Lisp, this might look strange and cryptic, but there are a few things you should notice. Not a single index variable. Not a single for loop. No chances to be off-by-one.

All of the functions are predictable. They all have return values. You don't have to think about whether your function call is going to return something or mutate something (or both).

The functions don't have internal state, so it's really easy to debug. Just figure out which arguments your buggy function got called with, and you can isolate it and reproduce it over and over.

The first two things that appear inside the merge sort function are utility functions to find and return the left half and the right half of the array. These are followed by the merge procedure, which happens recursively instead of iteratively.

There are four cases here. Two of them result in the final return value, and the other two cause a recursion. No unwieldy copying from one place to another.

The final cond statement is what kicks off the algorithm. The calls to mergesort appear as arguments to the call to merge. This is semantically pleasing because it expresses a truth about the algorithm that isn't expressed by the three sequential, mutative calls to mergesort, mergesort and merge in the C implementation.

What Next?

If you were a skeptic before, hopefully now, you can see how functional programming can help you write more elegant and understandable code. If you want to know more, check out The Little Schemer. It's a classic, and a gentle introduction to these ideas.