Implement a Bi-Directional Counter in Functional Programming?

Question

I'm trying to wrap my head around some Functional Programming basics.

So, by using a higher order function I can create a counter that can increment:

function counter( start ) {
  var count = start;
  return function() {
    return ++count;
  }
}

var myCounter = counter( 2 );
myCounter();
myCounter();

However, what would be the correct (in terms of Functional Programming) way of implementing a bi-directional counter? I came up with the following, but it seems too much like a cheap object for me:

function bicounter( start ) {
  var count = start;
  var mutate = function(amount) {
    return function() { count += amount; }
  };
  return {
    increment: mutate(1),
    decrement: mutate(-1)
  }
}

var myCounter = bicounter( 2 );
myCounter.increment();
myCounter.decrement();

Answer 1

Functional programming quite literally means “programming with functions”. Here, we are talking about a mathematical function and not a subroutine. What's the difference?

1. This is a function (the Ackermann function):

   

   A mathematical function is pure (i.e. it has no side effects). A mathematical function does only one thing: it maps an input value to an output value. It doesn't change the value of any variable.

2. This is a subroutine which computes the result of the Ackermann function:

   function A(m, n) {
       var stack = [], exit;
   
       do {
           if (m > 0) {
               m = m - 1;
   
               while (n > 0) {
                   stack.push(m);
                   n = n - 1;
               }
   
               n = 1;
           } else {
               m = stack.pop();
               n = n + 1;
           }
       } while (m !== exit);
   
       return n;
   }
   

   A subroutine may or may not be pure. For example, the above subroutine is impure because it modifies the variables m, n and stack. Thus, although it computes the result of the Ackermann function which is a mathematical function, yet it's not a mathematical function.

Now, consider your counter function:

function counter(count) {
    return function () {
        return ++count;
    };
}

var countup = counter(0);

alert(countup()); // 1
alert(countup()); // 2
alert(countup()); // 3

Is this functional programming? The short answer is, it's debatable because you are indeed using higher-order functions. However, your counter function isn't a mathematical function. Hence, in the strict definition of functional programming (i.e. programming with mathematical functions) your program isn't really functional.

Note: I think most of the confusion arises because in JavaScript first-class subroutines are called functions. Indeed, they can be used as functions. However, they are not mathematical functions.

Actually, your program is object-oriented. Every time you call counter you are creating a new abstract data type representing a counter object. Since this object has only one operation defined over it, you can get away with returning that operation itself from the counter function. Hence, your intuition is absolutely correct. This is not functional programming. It's object-oriented programming.

So how would you implement a counter using functional programming?

In functional programming, everything can be defined as a function. That's strange. What about numbers? Well, numbers can be defined as functions too. Everything can be defined as a function.

However, to make things simpler let's assume that we have some primitive data types like Number and that we can define new data types using structural typing. For example, any object that has the structure { count: Number } (i.e. any object with a single property named count which is of the type Number) is a value of the type Counter. For example, consider:

var counter = { count: 5 }; // counter :: Counter

The typing judgement counter :: Counter reads as “counter is a value of the type Counter”.

However, it's usually better to write a constructor to construct new data structures:

// Counter :: Number -> Counter

function Counter(count) {
    return { count: count };
}

var counter = Counter(5); // counter :: Counter

Note that the value Counter (which is a function of the type Number -> Counter, read as “Number to Counter”) is different from the type Counter (which is a data structure of the form { count: Number }). Types and values can have the same name. We know that they're different.

Now, let's write a function that returns the value of a counter:

// count :: Counter -> Number

function count(counter) {
    return counter.count;
}

It's not very interesting. However, that's because the Counter data type itself is not very interesting. In fact, the Number data type and the Counter data type are isomorphic (i.e. we can convert any number n into an equivalent counter c using the function Counter and we can convert the counter c back into the number n using the function count, and vice versa).

Hence, we could have avoided defining a Counter data type and used a Number itself as a counter. However, for pedagogical purposes let's use a separate data type for Counter.

So, now we want to update the value of counter using a function named increment. Hold on. Functions can't change the values of variables in functional programming. How do we update the value of counter? Well, we can't update the value of counter. However, we can return a new counter with an updated value. This is exactly what we do in functional programming:

// increment :: Counter -> Counter

function increment(counter) {
    return Counter(count(counter) + 1);
}

Similarly, we can define the decrement function:

// decrement :: Counter -> Counter

function decrement(counter) {
    return Counter(count(counter) - 1);
}

Notice that if we had used a Number as a Counter then the increment and decrement operations for a counter c would be defined as c + 1 and c - 1 respectively. That further strengthens our understanding that a counter is just a number.

That's all dandy but what's the point of functional programming?

Currently, it seems as though functional programming is more difficult than normal programming. After all, sometimes you really need to mutation to write interesting programs. For example, can you do this easily using functional programming?

function bicounter(count) {
    return {
        increment: update(+1),
        decrement: update(-1)
    };

    function update(amount) {
        return function () {
            return count += amount;
        };
    }
}

var counter = bicounter(0);
alert(counter.increment()); // 1
alert(counter.decrement()); // 0

Actually, yes you can do that using the State monad. I'll switch to Haskell for want of a better functional programming language than JavaScript:

import Control.Monad.State

type Counter = Int

counter :: Counter
counter = 0

increment = modify (+1)
decrement = modify (subtract 1)

alert = get >>= (liftIO . print)

program = do
    increment
    alert
    decrement
    alert

main = evalStateT program counter

This is a runnable Haskell program. Quite succinct isn't it? This is the power of functional programming. If you're sold on the idea of functional programming then you should definitely consider learning Haskell.