There are some rituals that need to be adhered to while learning a new language. One of them is writing the program to compute factorial. The implementation of factorial, like most other things in Clojure, can be done in many ways. This post examines 20 of the easiest ones.
All of these ways produce the correct result but only some are idiomatic. In this post we see some of those programs and figure out why a direct translation from an imperative language to Clojure does not produce optimum results.
Here is attempt #1 – a direct translation from the mathematical definition to Clojure code. We take an argument and if the number passed in is 1 we return 1 otherwise we decrement the argument and call the same function recursively.
(defn factorial1
[n]
(if (= n 1)
n
(* n (factorial1 (dec n)))
)
)
The invocation goes through fine. An invocation (factorial1 4) yields 24. This is on expected lines. There are some big problems though – this code’s complexity is exponential, the code is recursive and worst – it will run on JVM. JVM was never designed to execute industrial strength code. Expect undesirable results if you write and run recursive directly on JVM. Yeah! We are talking of stack overflow. This is a problem which shows up in poorly written code at the mode most inopportune moment – when your traffic is peaking, load is high and just too many people waiting on the results of your code.
Clojure (and for that matter Scala) need to deal with this problem at their level because it is not possible to change the JVM. Clojure’s solution to this is the loop/recur paradigm. This is at first looks like an odd combination – loop means to iterate and recur means to recurse. What are these two verbs doing together? That’s where the real power of Clojure comes into action. Let’s look at loop/recur for a while before looking at the recursion code. Loop/recur is a way of iteration as seen in the code below –
(loop [i 5]
(if (= 1 i)
(prn "Finishing the loop")
(recur (dec i) )))
The loop is kind of bookmark which tells recur where to come back to. The loop has an initialize block that gets executed once – during the first iteration. In this case I is getting set to 5. The loop has if which checks if index is 1 yet and prints a message if it does so. Otherwise we decrement the index and call the same set of instructions again. If you run this on a REPL all you are going to see is the message "Finishing the loop"
We can make some adjustments in the code here. We can keep an accumulator – a ‘variable’ that stores the net effect of the computation of all previous iterations. This concept holds the key to using recursion on JVM. If you write your code in such a way that the results of all previous iterations/recursive calls can be stored in a variable then the compiler does not need to store the stack frames for previous calls. In such scenarios the compilers do what is called as Tail Recursion Optimization. But for this optimization and overall recursion to work on JVM you need to learn to use the accumulator as shown here. Before going on to factorial, let’s write some code to add all integers upto a particular number n. Mathematically, we know the answer should be (n * (n+1) ) /2. So if we want to add first five ints it would be 5 + 4 + 3 + 2 + 1 = 15 = (5 * 4)/2 . Here is the code for this addition
(loop [i 5 accumalator 0]
(if (= 0 i)
accumalator
(recur (dec i) (+ i accumalator))))
Running the code produces expected results. The big change from the last time is we have a variable called accumulator, this is the variable holding results of all our computation till this stage. So, when the index variable equals zero we return whatever we have accumulated till now otherwise we recur using the decremented value and the modified accumulator.
Translating the above code from addition to factorial code cannot be a big leap. The code is almost identical as above but for the different operator and change in the identity value –
(loop [i 50 accumalator 1]
(if (= 1 i)
accumalator
(recur (dec i) (* i accumalator))))
120
A recur can target either a function definition or a loop. Here is the function definition variant -
(defn factorial2 [i accumalator]
(if (= 1 i)
accumalator
(recur (dec i) (* i accumalator))))
The only issue here is that we need to call it with two arguments (factorial2 5 1), which does not make sense because accumulator is our implementation detail and should not be exposed to the outside world. We can remedy that by using the multi-arity feature of Clojure. This feature allows you to call a function with variable arguments. (
For variable arguments in Scala, look here)
(defn factorial3
(
[i]
(factorial3 i 1)
)
(
[i accumalator]
(if (= 1 i)
accumalator
(recur (dec i) (* i accumalator)))))
One of the points to note is that when using multi-arity feature an extra set of () would be required. This is a trip point for many new Clojurists. This function can be invoked with both 1 and 2 arguments.
Although we have written the code in Clojure it doesn’t seem to take us forward much –
user=> user=> (factorial3 500)
ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1424)
user=> (factorial3 50)
ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1424)
user=> (factorial3 10)
3628800
We can rectify this scenario by using another cute Clojure trick – using *’ instead of *. This instructs Clojure to use ‘Big’ numbers and not the primitive data types. So here is another definition
(defn factorial4
(
[i]
(factorial4 i 1)
)
(
[i accumalator]
(if (= 1 i)
accumalator
(recur (dec i) (*' i accumalator)))))
This works –
user=> (factorial4 500)
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000N
user=>
We can write factorial using Clojure’s apply and reduce functions also as presented below
(defn factorial5 [i]
(apply * (range 1 (+ i 1))))
As you may have guessed this code creates a list in the range and multiplies them to produce the result. The range function produces the list from 1 to i and the
apply function ‘applies’ * on all its arguments which happen to be the elements of this list. Similarly, we can use the reduce function –
(defn factorial6 [i]
(reduce * (range 1 (+ i 1))))
Range is one way of generating lazy sequence in Clojure, iterate is another. Here are the corresponding ways to implement factorial using iterate –
(defn factorial7 [i]
(reduce * (take i (iterate inc 1))))
(defn factorial8 [i]
(apply * (take i (iterate inc 1 ))))
Another way of using range to calculate factorial would be to use the range function to create a list and utilize the homoiconicity of Clojure by prepending the *’ operator and using eval. Here are the two variants –
(defn factorial9 [i]
(eval (cons '*' (range 1 (inc i)))))
(defn factorial10 [i]
(eval (cons '* (take i (iterate inc 1 )))))
Remember we are cons-ing *’ so the expression ends up looking like a ‘*’ , this I have deliberately avoided in definition of factorial10. The output run is shown below –
user=> (factorial9 50)
30414093201713378043612608166064768844377641568960512000000000000N
user=> (factorial10 50)
ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Num
bers.java:1388)
user=> (factorial10 5)
120
Let us now turn our attention to other ways of generating and using lazy sequences – after all using lazy sequences is the hallmark of any functional programming language, even if it is hybrid functional.
Here is method# 11 to generate factorial –
;;;;;;;;;;;;
(defn afact [n v]
(let [next-n (inc n) next-v (* n v)]
(cons v (lazy-seq (afact next-n next-v))))
)
(defn factorial11 [i]
(nth (afact 1 1) i))
Trampolining is another useful trick. The code below uses it to generate factorials –
(defn factorial12
([i] (trampoline (factorial12 (dec i) i)))
(
[i a] (if (<= i 1) a #(factorial12 (dec i) (* i a)))
)
)
Up comes number 13. Number 13 has traditionally been considered unlucky. Let’s reinforce that belief by writing some non-idiomatic Clojure code. The code works but is not the Clojure way of doing things –
(defn factorial13 [i]
(do
(def answer 1)
(def x 0)
(while (< x i)
(def x (inc x))
(def answer (* x answer))
)
answer
)
)
And you could do the same stuff like this trading do whole for dotimes –
(defn factorial14 [i]
(do
(def a 1)
(dotimes [index i]
(def a (* a (inc index)
)
)
)
)
a)
Up at number 15 is the continuation of the theme we started in number 13. This code takes the theme a notch higher and uses atom to create a local scope.
(defn factorial15 [i]
(let [a (atom 0)
res (atom 1)
]
(while (> i @a)
(swap! res * (swap! a inc)
)
)
@res)
)
So, having look at three idiotic and non-idiomatic ways of writing factorials, let’s write a few idiomatic ones. Let’s try with pmap first. Here is the code that uses pmap and computes factorial
(defn factorial16 [i psz]
(let [parts (partition-all psz (range 1 (inc i)))]
(reduce * (pmap #(apply * %) parts))))
Here is another one using pvalues –
(defmacro factorial17 [i psz]
(let [exprs (for [p (partition-all psz (range 1 (inc i)))]
(cons '* p))]
`(fn [] (reduce * (pvalues ~@exprs)))))
And here is another one using pcalls
(defmacro factorial18 [i psz]
(let [exprs (for [p (partition-all psz (range 1 (inc i)))]
`(fn [] (* ~@p)))]
`(fn [] (reduce * (pcalls ~@exprs)))))
Finally, here is a concise yet simple one
(def factorial19
(map first
(iterate
(fn [[p n]] [(* p n) (+ 1 n)]) [1 1])))
(nth factorial19 5)
Coming at # 20 – Use the wonderful
Incanter.
Know what? There are at least 15 more not-so-exasperating ways of writing factorial in Clojure! Will leave those for a future post.
