Accumulators in Haskell

(CW: coding exercise/study with zero higher purpose.)

In Paul Graham's 2002 essay, Revenge of the Nerds, Graham suggests one metric for the expressive power of a programming language: the ease of writing an accumulator.

[An accumulator is] a function that takes a number n, and returns a function that takes another number i and returns n incremented by i.

For example:

x = accumulator(7);
x(1); // 8
x(3); // 11
y = accumulator(-1);
y(1); // 0

In the parlance of OOP, an accumulator is a NumberIncrementerFactory. In the parlance of programming language theory, an accumulator produces a canonical example of a closure: a function together with a stateful external environment.

Graham uses the relative difficulty of writing accumulators in various languages to demonstrate the elegance/clumsiness of writing non-trivial code in them. (Of course, along with any notion of a metric comes Goodhart's law: a metric stops measuring anything useful if people start treating it as a target. If there are joke languages purpose-built to make writing quines easy, you can bet someone's written a language where there are accumulators as a language primitive.)

For the hell of it, I decided to write one in Haskell. This was a bad idea — while implicit closures are the sine qua non of many functional programs under the hood, state is most certainly not.

To maintain implicit state we need to be working under some monad; I picked the IO monad as it was the most natural fit for declaring new persistent variables (courtesy of the IORef library). (A State monad wouldn't have worked as the outer layer, since running an accumulator changes the state space that the program is storing.)

Thus our example from above translates like so:

import Accumulator

main = do
    foo <- accumulator 7
    foo 1 >>= print -- 8
    foo 3 >>= print -- 11
    bar <- accumulator (-1)
    bar 1 >>= print -- 0

...while our implementation begins with the following preamble:

module Accumulator (accumulator) where
import Data.IORef

accumulator :: (Num a) => a -> IO (a -> IO a)

(N.B. (Num a) => approximately means for any type a for which addition is defined. If we didn't want polymorphism [which Graham stipulates as a requirement], we could have just used Int -> IO (Int -> IO Int).)

A quick sanity check of the type signature: the accumulator takes a number and creates (i.e. returns from the IO monad) something capable of taking numbers and creating new numbers based on them. That sounds like the interface we want. (See further below for an example of another plausible looking type signature that doesn't work.)

From there we fill in the implementation:

accumulator init = do
    x <- newIORef init
    return $ \i -> do
        modifyIORef x (+i)
        readIORef x

The code runs and outputs the expected values. Further internet searching reveals that Malcolm Wallace and Tom Pledger already wrote this exact code back when the essay originally came out. So, on the one hand, this was probably a waste of time; on the other hand, it's always good to try it oneself, right?

Were the nested IOs necessary?

Let's look at that type signature again (substituting a with Int for readability's sake): Int -> IO (Int -> IO Int)

Do we really need to have an IO function returned by an IO function? Wouldn't it be fewer layers and simpler to have a type signature more like this?:

accumulator :: Int -> Int -> IO Int

main = do
    let foo = accumulator 7
    foo 1 >>= print -- 8
    foo 3 >>= print -- 11
    let bar = accumulator (-1)
    bar 1 >>= print -- 0

Sadly this is logically unsound. Imagine such an implementation existed. Then consider the following two programs:

main = do
    let foo = accumulator 0
    let bar = accumulator 0
    foo 1 >>= print -- 1
    bar 1 >>= print -- 1

main = do
    let foo = accumulator 0
    let bar = accumulator 0
    foo 1 >>= print -- 1
    foo 1 >>= print -- 2

But then since foo is exactly equal to bar, the two programs should behave identically! So nothing with this type signature can behave like an accumulator.