Moving from an Imperative to a Functional Way of Thinking
This blog is the second in a series (of unknown length) about how you need to rearrange your thought processes in order to move from the imperative style of programming to the functional style.
Calculating the Fibonacci Sequence
The problem we’ll tackle is calculating the nth number in the Fibonacci sequence. For those who can’t remember, the Fibonacci sequence is formed by starting with the numbers 0 and 1 and then adding the first number to the second to produce a third. Then you add the second number to the third to produce the fourth, then the third to the fourth to produce the fifth etc. like so:
Start Values => 0, 1 0 + 1 = 1 => 0, 1, 1 1 + 1 = 2 => 0, 1, 1, 2 1 + 2 = 3 => 0, 1, 1, 2, 3 2 + 3 = 5 => 0, 1, 1, 2, 3, 5 3 + 5 = 8 => 0, 1, 1, 2, 3, 5, 8 5 + 8 = 13 => 0, 1, 1, 2, 3, 5, 8, 13
The code sample shown below is structured as a loop. We go around that loop as many times as needed to calculate the nth number in the sequence. The variables
b hold the
n-1 numbers in the sequence, and the variable
sum holds the nth number.
But notice how much coding effort we’ve had to expend to achieve this result. We have had to write code that:
- Identifies that a block of code needs to be executed multiple times
- Manages the loop index counter (called
n) by first testing its value at the start of every loop iteration, and then decrementing its value at the end of each loop iteration
- Manually tracks the value of the final result in a variable called
- Manually shunts the values of
This type of solution is typical of a program written in the imperative style. As the developer you are concerned about how the final result is to be calculated, and consequently, you are also concerned about exactly when specific instructions must be performed. As a result, we have developed a style of coding that often diverts our attention away from what needs to be done, because we’ve become preoccupied with the how and when of what we’re doing.
All we actually need to do here is add up a sequence of numbers so that term sn = sn-1 + sn-2. As much as possible, we should delegate the task of figuring out how and when specific instructions should be executed to the tools provided by the programming language. By taking this approach, it frees us up to think about what needs to be done without becoming distracted by the mechanical processes required to achieve it.
This is the rationale of functional programming. (To put that in more technical terms, we are focussed on writing a program that implements the principle of Referential Transparency, but let’s not worry about that now.)
Rethinking the Solution
So rather than trying to perform some sort of line-for-line conversion, we need to stop and take a step back (and probably also a deep breath) and look at what we want to achieve. Then we can focus on designing the functions that achieve this goal, without being side-tracked by the mechanics of how the result will be constructed. In other words, we need to understand what tools the Clojure language offers us, and then set about composing those tools into a solution that meets our needs.
First, let’s look at the data structure with which we’re working. The Fibonacci series is a simple number sequence in which the next term is always the sum of the previous two terms. So a good place to start will be to create a Clojure function that, given a pair of terms [sn-2,sn-1], gives back the pair [sn-1,sn]. In other words, its a function that takes one step further along the Fibonacci series.
Let’s call this function
user=> (defn fib-step [[a b]] [b (+ a b)]) #'user/fib-step user=> (fib-step [0 1]) [1 1] user=> (fib-step [1 1]) [1 2] user=> (fib-step [5 8]) [8 13] user=>
At this point, its probably worth explaining some Clojure syntax here, since the double square brackets might be puzzling you:
When defining a function in Clojure, you will typically use the
defnmacro. The first parameter to this macro is the function name (in this case
fib-step) and the second parameter is a list containing all the parameters the function will receive. Since a list is required, we must use square brackets – so this explains the outer pair of square brackets.
At this point we could simply provide variable names for each of the parameters this function receives; however, I wanted to design the function so that it receives a single list, within which are a pair of numbers. Clojure has a neat feature called “destructuring” that allows the contents of a structured value to be unpacked and each part assigned to an individual variable.
So rather than simply giving the first parameter a name such as
fib-pairand then unloading this list later in the code, we can get Clojure to unpack (or destructure) this list for us and assign the parts to the vars
So the inner pair of square brackets are used to indicate that the first (and only) parameter is a list.
binside this list are the vars to which Clojure will assign the first and second items of the list.
Well, that’s a good start – but how can we make use of a function like this? Also, this function only works if you know the previous pair of numbers in the sequence, so the calculation will always have to start from the beginning of the list.
This is true. Fortunately, Clojure implements the concept of “lazy” data structures. A data structure is said to be lazy if you specify how to calculate the contents, but never perform that calculation until you actually need the data. So the next thing to do is to create a lazy sequence of all possible entries in the Fibonacci series.
Clojure has a function called
iterate which takes two arguments, a function and a starting value. The result is a lazy sequence in which the starting value is the first item. The second item is created by calling the function with the starting value as its argument. This produces some value that then becomes the second item in the sequence. The third item is then created by passing the second item as an argument to the function etc., and so on ad infinitum.
If you have Clojure installed and have started a REPL, enter the above definition for
fib-step and then issue this command:
user=> (iterate fib-step [0 1]) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1501) ([0 1] [1 1] [1 2] [2 3] [3 5] [5 8] [8 13] [13 21] [21 34] [34 55] [55 89] [89 144] [144 233] [233 377] [377 610] [610 987] [987 1597] [1597 2584] [2584 4181] [4181 6765] [6765 10946] [10946 17711] [17711 28657] [28657 46368] [46368 75025] [75025 121393] [121393 196418] [196418 317811] [317811 514229] [514229 832040] [832040 1346269] [1346269 2178309] [2178309 3524578] [3524578 5702887] [5702887 9227465] [9227465 14930352] [14930352 24157817] [24157817 39088169] [39088169 63245986] [63245986 102334155] [102334155 165580141] [165580141 267914296] [267914296 433494437] [433494437 701408733] [701408733 1134903170] [1134903170 1836311903] [1836311903 2971215073] [2971215073 4807526976] [4807526976 7778742049] [7778742049 12586269025] [12586269025 20365011074] [20365011074 32951280099] [32951280099 53316291173] [53316291173 86267571272] [86267571272 139583862445] [139583862445 225851433717] [225851433717 365435296162] [365435296162 591286729879] [591286729879 956722026041] [956722026041 1548008755920] [1548008755920 2504730781961] [2504730781961 4052739537881] [4052739537881 6557470319842] [6557470319842 10610209857723] [10610209857723 17167680177565] [17167680177565 27777890035288] [27777890035288 44945570212853] [44945570212853 72723460248141] [72723460248141 117669030460994] [117669030460994 190392490709135] [190392490709135 308061521170129] [308061521170129 498454011879264] [498454011879264 806515533049393] [806515533049393 1304969544928657] [1304969544928657 2111485077978050] [2111485077978050 3416454622906707] [3416454622906707 5527939700884757] [5527939700884757 8944394323791464] [8944394323791464 14472334024676221] [14472334024676221 23416728348467685] [23416728348467685 37889062373143906] [37889062373143906 61305790721611591] [61305790721611591 99194853094755497] [99194853094755497 160500643816367088] [160500643816367088 259695496911122585] [259695496911122585 420196140727489673] [420196140727489673 679891637638612258] [679891637638612258 1100087778366101931] [1100087778366101931 1779979416004714189] [1779979416004714189 2880067194370816120] [2880067194370816120 4660046610375530309] [4660046610375530309 7540113804746346429]user=>
This is to be expected since the
iterate function is designed to run forever; so never use it without first wrapping it in some other container such as a function or a var. Fortunately, an integer overflow exception prevents this function from running forever and locking up the REPL!
However, even though this code sample crashes, it demonstrates that iterating the simple function
fib-step is all that’s need to generate successive pairs of numbers in the Fibonacci series.
But we’re not quite where we need to be yet.
fib-step produces a sequence in which each item is a pair of numbers. We’re not interested in the second number of each pair because we know that this value is repeated as the first number in the next pair. So we need to keep only the first number in each one of these pairs. The easiest way to do this is to map the function
first across all the elements in the sequence produced by
user=> (map first (iterate fib-step [0 1])) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1501) user=>
Well OK, but this still doesn’t prevent the
iterate function from spinning out of control. This is because we have not yet said which element of this sequence we’re interested in. Without placing a limit on how many items iterate should produce, it will just run out of control forever (or until it explodes due to some exception).
However, we can prevent
iterate from exploding by storing the lazy sequence in a var.
user=> (def fib-seq (map first (iterate fib-step [0 1]))) #'user/fib-seq user=>
Now we have lazy sequence called
fib-seq from which we can take any number of items in the Fibonacci series.
user=> (nth fib-seq 10) 55 user=>
But we can do more than just taking the nth item from the list. Let’s say we want to see the first 20 items in the list: no problemo…
user=> (take 20 fib-seq) (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181) user=>
No prizes for guessing what the
take function does…
So the entire Clojure solution occupies only 2 lines of code! Here's what you would enter into the REPL.
user=> (defn fib-step [[a b]] [b (+ a b)]) #'user/fib-step user=> (def fib-seq (map first (iterate fib-step [0 1])) #'user/fib-seq user=>
Notice how different this solution is compared to the imperative solution. We have solved the problem of obtaining the nth item from the Fibonacci series by writing one very simple function called
fib-step. The lazy sequence this creates is stored in the var
fib-seq. When compared to the imperative solution, the functional solution is more:
- Compact – one very simple function and one lazy sequence variable
- Expressive – the code focusses on exactly what needs to be done, without needing to care about the mechanics of how to manage things like loops or index variables etc.
- Versatile – the
fib-seqvar contains the entire Fibonacci sequence from which we can extract as many or as few items as we need
The challenging part is overcoming the fact that this style of solution requires a completely different mental approach to solving the problem – and one that is at first alien to the mind of an imperative programmer. However, I trust you are now starting to see the direction in which this change (or mind shift) should proceed, and consequently you should start to appreciate the power and simplicity of this way of programming.
Have fun bending your brain!
All source code from the Mindshift blog series can be found on GitHub