I did a clojure thing!
So I've been trying to learn clojure and as it happens we did some mathematical expression parsing. Which if anyones looked at my github you can see I've done quite a bit of :P
Well so after helping a bunch of classmates getting it implemented in java, I thought this would be perfect for trying to do in clojure. Functional programming lends itself to pattern matching fairly easily I've heard at least. Although that example was for haskell, I thought there should be no problem in clojure.
I started by implementing the Shunting Yard algorithm in clojure. But quickly realized that since I'm working with immutables, while loops and pushing and poping things on stacks isn't really optimal.
So I started thinking about how to do this functionally, and remembered how mr. Hickey went on and on about "recur" and how it allows for stackless-recursion (tail-call elimination) now it wasn't too difficult imagining how to turn the alorithm from using loops to recursion, instead of writing the state, I just recall with the new one instead.
So for some examples instead of a typical iterative way of adding to a list:
def addKtoN(l,k,n): for i in range(k,n): l.append(i) return l
Where we iterate over a loop and modify state inside the loop every time.
Rewriting this in a recursive style can be done like so:
(defn addKtoN [l,k,n] (if (>= k n) l (recur (conj l k) n (inc k))))
As you can see the step where we "add" the item to the list:
(conj l k)
we don't really modify l, we just call the function again with a new list containing all the elements of l with i added to the end (or "conjoined" as the function is called).
So using this way of moving the "assignment" into a recursive call,
I could translate the iterative algorithm from wikipedia to clojure.
And after that I got a little help from a few friends over at #clojure on freenode, and we were able to clean up the code a little bit, as I'm fairly new to clojure and don't know all the functions they had plenty of knowledge of moving the logic in more concise steps, which all in all made the whole function really clean looking.
Now the "project" is on github if you wanna have a look, after implementing the infix to postfix algorithm I used the same method to make an evaluator for the postfix expression result.posted on: Sept. 17, 2016, 2:02 a.m. by: Andreas Larsen, permalink