Functional Programming: Accumulators

Functional programming is quite different from Object Oriented Programming (OOP). I greatly prefer OOP to Functional, but suffered through Functional in class. Functional Programming can be mind boggling at times. To me, it didn’t seem like a normal mode of thinking due to recursion. Recursion is arguably the most important building block of Functional Programming. Simply put, it is when a function repeatedly calls itself. A classic example of a recursive function is the famed Fibonacci Sequence in which, following the initial numbers of 0 and 1, each successive number is the sum of its two predecessors. This results in the sequence: 0, 1, 1, 2, 3, 5, 8 and so on. After some time, however, we learned about accumulators.

An accumulator is an additional argument added to a function. As the function that has an accumulator is continually called upon, the result of the computation so far is stored in the accumulator. After the recursion is done, the value of the accumulator itself is often returned unless further manipulation of the data is needed. To show this, let’s look at an example.

The following code is in OCaml — a functional programming language. The function reverses a list of input data of any type and has a linear runtime (n, the size of the input list). This means that it iterates through the input data to yield a result only once. This is much faster than the runtime of reverse without an accumulator which is n^2 where n is the size of the input list.

let reverse : ’a list -> ’a list =

let rec _reverse (acc : ’a list) : ’a list -> ’a list = function

| [] -> acc

| hd :: tl -> _reverse (hd :: acc) tl

in _reverse []

To describe the basics of it, the let is a function declaration, “reverse” is the name of the function, “’a list -> ‘a list” is the type signature of it (it takes in data of type ‘a list and returns data of type ‘a list), let rec is the method declaration of a recursive helper method inside of the larger method declared by the let and (acc : ‘a list) is the output which is an accumulator. For more specifics, the line “| [] -> acc” means that when the input data is empty (all of the elements have been stripeed from it in recursive calls), return the accumulator. That is called the base case of the function. The “hd :: tl” in the next line refers to the input list where hd is the first element of that list and tl is the remainder of it. Lastly, the “_reverse (hd :: acc) tl” portion of it means that the head of the list should be appended onto the accumulator wand then the tail of the list should be fed back into the recursive call.

Say we feed in the list [1, 2, 3] to this function. Initially, the accumulator is empty and we append 1 to the front of that empty list. This yields a list of [1]. Next, 2 is appended to the front of this, yielding [2, 1]. Lastly, 3 is appended to the front of that, yielding [3, 2, 1]. The runtime of this funciton is linear since we only iterate through the data once.

While the concept might seem basic to OOP programmers, it was quite eye opening as I expanded my horizons in functional programming beyond recursion without it.