Simple infix math calculation

This is my last post in a series in which I go through the exercises presented at the introductory Clojure workshop at Reaktor Dev Day 2013. Check out part 1 and part 2 as well.

I didn’t have time to even look at the last exercise during the workshop so for this blog post I decided to try and solve it without looking at the solution first, and then compare mine with the organizers’ solution.

The task was to implement a function that calculates math expressions given in infix notation (that is ‘1+1’ instead of the prefix notation (+ 1 1) we are used to in Clojure). The task was highly simplified as there were no requirements for operator precedence or handling of parentheses.

So here is my solution with and without detailed commentary:

(defn calc [& symbols]
  (loop [acc (first symbols)
         syms (rest symbols)]

    (if
        (empty? syms) acc
        (recur ((first syms) acc (second syms)) (nthrest syms 2)))))

;; Note that this calculates naively from right
;; to left without considering order of operations
(= 7  (calc 2 + 5))
(= 42 (calc 38 + 48 - 2 / 2))
(= 8  (calc 10 / 2 - 1 * 2))
(= 72 (calc 20 / 2 + 2 + 4 + 8 - 6 - 10 * 9))

And here is the more detailed walk-through of the solution:

;; Define a function `calc` that takes a variable number of arguments which will
;; be available in the sequence `symbols`
;; (No sanity checking of input here, you could call (calc 20 +) and break it)

(defn calc [& symbols]

  ;; Loop works like `let` (we can bind values to local names and then use them
  ;; inside expressions within the loop. In addition, from inside the loop, we can
  ;; call `recur` with the same number of arguments as the loop has bindings,
  ;; which will jump the execution back to the beginning of the loop with the
  ;; values `recur` was called with bound to the names

  (loop

      ;; Our loop has two bindings `acc` for accumulator and `syms` for
      ;; the remaining symbols to be processed. `acc` is initialized with the
      ;; first symbol from the input symbols (this should always be a number
      ;; in the kinds of infix expressions we support).
      ;; `syms` is initialized with the `rest` (everything but the first)
      ;; of the input symbols

      [acc (first symbols)
       syms (rest symbols)]

    ;; Inside the loop we always do a simple `if` on whether there are remaining
    ;; symbols or not

    (if (empty? syms)

      ;; If there are no symbols left to process, we return what the value of the
      ;; accumulator is

      acc

      ;; If there are symbols left, we `recur` back to the beginning of the loop,
      ;; with the following parameters

      (recur

       ;; To get the next acc value, we take the first element from the
       ;; remaining symbols, treating it as a function, and give it the current
       ;; value of `acc` and the next remaining symbol as parameters.
       ;; E.g. if `acc` were currently 20 and syms were [+ 3 * 4 ...], the
       ;; first parameter to recur would be (+ 20 3) or 23

       ((first syms) acc (second syms))

       ;; The second parameter is the rest of the remaining symbols. Because
       ;; each pass of the loop processes two elements from the sequence of 
       ;; symbols, we use `(nthrest coll 2)` which with the parameter 2 returns 
       ;; the rest of the given collection except for the first two elements

       (nthrest syms 2)))))

And then for comparison, the workshop organizers’ solution:

(defn calculator [& xs]
  (loop [res (first xs) ops (rest xs)]
    (if (empty? ops)
      res
      (recur ((first ops) res (second ops))
             (rest (rest ops))))))

Amusingly the solutions turn out to be basically identical. The only difference besides naming is the use of `(nthrest coll 2)` versus `(rest (rest coll))`

The solution and the whole problem are quite simple: take the first number from the input as the starting accumulated value. Then process the remaining arguments in chunks of two, always applying the first of the chunk as a function to the current accumulated value and the second value of the chunk, storing the result as the new accumulated value. Repeat this until there are no elements left and accumulator will contain the final result.

It actually took me quite a while to arrive at the solution. Although I had some faint gut feeling that this calls for recursion, I kind of avoided going there at first, trying different variations of somehow trying separate the numbers from the operators and then trying to “map the operators” over pairs of numbers, but that started to feel too complicated pretty quickly.

After a while it just hit me how to get it done with loop and recur since I had recently used them for the first time in another example. I think I partly tried to avoid going to loop/recur because in Clojure Programming Emerick et al. tell that:

recur is a very low-level looping and recursion operation that is usually not necessary:

When “iterating” over a collection or sequence, functional operations like map, reduce, for, and so on are almost always preferable.

So I assume this problem could probably be solved with reduce (or some combination of map, reduce, .. ) as well. I might try that and add the additional solution to this post later unless someone wants to beat me to it and include one in the comments. 🙂

Edit: Looks like this exercise was taken from 4Clojure: Infix Calculator

Advertisements

3 comments

  1. Could you do something like:

    (fn left-to-right [& symbols]
    (reduce #((first %2) %1 (second %2)) (first symbols) (partition 2 (rest symbols))))

    That is, because the infix to prefix translation of:

    a + b / c * d
    is
    (* ((+ a b) / c) d)

    You can then use the natural recurrence of reduce to store your intermediate variables.

    I too have a deep desire to chase recur/gotos out of my Clojure code.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s