# Writing an Infix Calculator in Clojure

2014-03-16

A common problem in the Lisp world involves demonstrating how in spite of the language's use of prefix notation, it is so robust as to allow for infix notation at the same time.

In other words, normally, we might put together a series of mathematical calculations like this:

``````(/ (- (+ 38 48) 2) 2)
``````

Alternatively, we could also write a function to support the following, as well:

``````(infix 38 + 48 - 2 / 2)
``````

Let's look at how the `infix` function might be written. A common Lisp style would be to write the function using recursion. We would treat the arguments to `infix` as a stack, pulling them off one at a time and operating on an accumulator.

``````(defn infix [val & others]
(loop [acc   val
stack others]
(if (empty? stack)
acc
(let [op  (first stack)
b   (second stack)
rem (rest (rest stack))]
(recur (op acc b) rem)))))
``````

Above, we treat the first argument to `infix` as the accumulator `acc` which will hold the result of the various operations. The `stack` binding will hold all the remaining operations and numbers. Our base case occurs when the `stack` binding is empty, at which point we hand back our accumulator and have a result. Otherwise, using `let` for clarity, we bind an operator `op`, the first element from the `stack` list, and a number `b`, the second element. What remains will be everything from the third element onward, what is slightly clumsily done here with two calls to `rest`. With the bindings in place, we make a recursive call to `infix`, this time passing the result of the operation on the accumulator and our next number, as well as the remaining operations or numbers.

What makes the problem interesting is its highlighting how easy it is to store functions like `+`, `-`, `*`, and `/` in a list and then later call them. In particular, in my mind, it's the line `(op acc b)` that shows how cool a Lisp can be.

Now the solution above is rather verbose. The use of `loop` and `recur` comes from my having learned Lisp with The Little Schemer. In writing Clojure code, I find it helpful to start with a recursive algorithm using `loop` and then refactor towards a tighter implementation when possible.

A cleaner implementation of `infix` in Clojure might look something like the following. (N.B. The code below is not my own and is taken from the collection of solutions to problem 135 on 4clojure.)

``````(defn infix
([x op y]
(op x y))
([x op y & xs]
(apply infix (cons (infix x op y) xs))))
``````

By defining two method signatures with distinct arities, we can set up our list of numbers and operations, and then call `apply` with our simple method signature to get a result.

Taking the example above, i.e., `(infix 38 + 48 - 2 / 2)`, our initial call to `infix` takes the first three elements from the passed arguments, e.g., `38`. `+`, and `48`, and calls `infix` again, this time using the simple `(op x y)` code. From there, we call `cons` with `86` and `(- 2 / 2)`, to get the list `(86 - 2 / 2)`. From there, it's a simple matter of invoking our `infix` method on the list, which will produce a solution.