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))))))
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:
recuris a very low-level looping and recursion operation that is usually not necessary:
When “iterating” over a collection or sequence, functional operations like
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. 🙂