My Clojure explained solutions to the s99 problems 1 to 3
15/07/2010 1 Comment
A year (or maybe more) ago, I started toying with emacs and soon had to tweak its configuration file, which is actually a program written in elisp, a variant of the lisps family.
I had no former experience with anything like lisp before, and anytime I touched the .emacs file, a pile of weird error messages would show up when starting emacs. So I thought it might be a good idea to learn the lisp’s syntax so I’d at least know what was that unbalanced quote I kept seeing in .emacs snippets in the internets.
With time, I started appreciating more and more lisp’s minimalistic syntax, and here I am now, spending more and more time toying with Clojure, a modern Lisp variant that runs on the JVM (my platform of choice, being a Java developer for a couple of years already).
Before that, I learned me some Scala, and to help myself get rid of my imperative programmer reflexes (for loops, variables, etc.), I started coding the solutions for the excellent s99 problems using Scala. It was a joyful although painful experience: Painful because my mind would find the imperative solution first, but I had to refrain from using it while knowing that Scala’s constructs would let me do it, and rather keep reminding myself that the functional solution would have no variables. Joyful because I had to challenge my thought process to not pick the familiar path and tackle problems differently.
Now that I’m trying to learn Clojure, I figured I’d do the same and solve the s99 problems using Clojure. The problems are generic enough and not tied to any specific language.
In the following you’ll find the first 3 problems and their (hopefully) explained solutions.
Disclaimer: I’m still in my baby steps with Clojure and did the best I could with the little I know so far. I would be glad to hear the other clojurists opinions on my approach and any constructive criticism.
Find the last element of a list.
user> (last ‘(1 1 2 3 5 8))
My one-liner solution:
(defn last-99 "P01" [l] (reduce #(do %2) l))
I'm reducing the list and only keeping the second element. The reduce function would apply its first argument (a function) on the first 2 elements of the list, then on the result of this application and the third list element, etc.
Here's how the reduction function would walk the list '(1 1 2 3 5 8) :
I highlighted the result and the first argument of every line to visually show that the result of a reduction is fed as an argument to the next reduction.
Another solution relying only on basic list functions (first and rest, who with cons are the bare minimum operations you need with lists to implement almost all the other list operations) would be:
(defn last2 "P01" [l] (if (empty? (rest l)) (first l) (last2 (rest l))))
The version will test if the list without its first element (rest) is empty, if so it'll return the first element and if not, it'll return the last element of the list remainder. Another way to view this is that the last2 function would consume the first element of the list until there remains only one, and return it.
Find the last but one element of a list
user> (penultimate '(1, 1, 2, 3, 5, 8))
Another one-liner solution:
(defn penultimate "P02" [l] (first (rest (reverse l))))
Basically I return the first item of the list after reversing it and removing its first element. For the list '(1 1 2 3 5 8), this would go as :
reverse: (8 5 3 2 1 1)
remove the head: (5 3 2 1 1)
return the first item: 5
I'm not very happy with this solution as it relies on reverse, a rather complex operation. It's like implementing multiplication using the power or sine function. Besides, the 5th problem is about implementing reverse. Another simpler (in that it only uses first and rest) solution would be :
(defn penultimate2 "P02" [l] (if (empty? (rest (rest l))) (first l) (penultimate2 (rest l))))
This solution, while being longer, only relies on basic functions (empty?, rest and first).
Find the Kth element of a list.
By convention, the first element in the list is element 0.
user> nth(2 '(1, 1, 2, 3, 5, 8))
Yet another one-liner solution:
(defn nth-s99 "P03" [n l] (if (zero? n) (first l) (nth-s99 (dec n) (rest l))))
This solution relies on the following principle: the 3rd element of a list is the 2nd element of that list without its first element. Applying this principle on the second statement would give that the 2nd element of a list is the 1st element of that same list without its first element.
It would the go that finding the nth element of any list can be brought back to finding the first element of a list. The trick is to remove the list's first item n times, which is exactly what the solution shown above does.