Skip to content
January 28, 2013 / Alex Miller

Next meeting Jan 29th – fun with monads

Next meeting of the Clojure Club is Tuesday Jan 29th, 11:30 am at Revelytix. Michael Bradley will be taking us on some monadic excursions in his code. Food will be provided!

November 29, 2012 / Alex Miller

Roman numeral kata

Yesterday, we held the November Clojure lunch club meeting – it was great to see some new faces (Michael and Matthew) and know there were a couple more people working with Clojure in St. Louis.

We worked on the Roman Numeral kata, basically just converting between Roman numerals and decimal numbers. We first tackled converting decimal to roman. Our first attempt looped over the (diminishing) decimal value, checking a set of conditions to determine what to pull out of the decimal and emit as the next largest Roman numeral.

This approach worked but no one felt good about the big set of cases so we refactored it to be based on a data table. This approach requires looping instead over the set of roman numeral values from big to small, repeatedly tearing off the appropriate hunks.

(def numerals {1 "I",
               4 "IV",
               5 "V",
               9 "IX",
               10 "X",
               40 "XL",
               50 "L",
               90 "XC"
               100 "C",
               400 "CD",
               500 "D",
               900 "CM",
               1000 "M"})

(defn to-roman [decimal]
  (loop [[num & r :as nums] (reverse (sort (keys numerals)))
         roman ""
         d decimal]
    (if num
      (if (>= d num)
        (recur nums (str roman (get numerals num)) (- d num))
        (recur r roman d))
      roman)))

In the main loop we have three variables:

  • nums – The sequence of roman numeral values still to try. These are destructured into the first num and a sequence r of the rest of the them while preserving the whole sequence as nums. This is initialized from our data table by just sorting the keys in descending order (1000, 900, …).
  • roman – The accumulator of the end value, initialized to empty string
  • d – The remaining decimal value to be converted, initialized to the input

In each step of the loop, we have three cases:

  • We still have numerals to try and the d has enough left in it to catch the current numeral – in this case, remove the value of the numeral from d, and prepend the roman numeral to the accumulator.
  • We still have numerals to try and d does NOT have enough left in it to apply to the current numeral – in this case, drop the current numeral and try the next one.
  • We have no numerals left to try – just return the accumulated value.

One key insight we had during this change was to treat the two-letter combinations (like IX) as a numeral value instead of special-casing. We suggested writing some code to generate the numerals table for a smaller starting table. That still appeals to me, but certainly would have been more effort than it was worth.

At this point we did some more testing to satisfy ourselves that it was working. I did not preserve the tests but we just applied to-roman to a range of inputs and eyeballed them, then did some spot checks for larger ones (1492, 1977, etc).

Next we tackled the from-roman as the inverse of to-roman, pulling off the first character (or two!) from the input roman numeral and adding its value to an accumulated decimal. We knew we needed a data table for this one as well so we worked in the repl to munge our prior table till we had something that looked useful, then encoded the process of producing it as a digits table. We ended up reworking that on our second pass.

I did not preserve our first attempt at the from-roman code unfortunately. It worked but had a lot of brute force conditions in it. The digits table was unnecessarily complicated. This is our second pass at cleaning it up:

(def digits (apply hash-map (mapcat reverse numerals)))

(defn from-roman [roman]
  (loop [[c1 c2 & r] roman
         d 0]
    (if-let [num (and c2 (get digits (str c1 c2)))]
      (recur r (+ d num))
      (if-let [num (get digits (str c1))]
        (recur (apply str c2 r) (+ d num))
        d))))

We loop through the roman numeral and pull off the first char, second char, and the rest of the chars, accumulating our final answer into d.

For each pass of the loop, if there are at least two characters in the roman numeral, we look up that two-char sequence in the digits table. If we find it (ex: IX), then we recurse with the rest of the chars and the accumulated value. If we don’t, then we try again with just the first character (ex: X) – note that this also nicely outlines the no chars case which will do a lookup of nil and return nil (all other should be found).

We had a bug in our first refactoring to this form in recombining c2 back into r (weren’t using apply). Since we had to-roman and from-roman, we were testing by round-tripping over a range of values and checking for equality. We were seeing about 20% failures over the range 1:10000. We found an example value that failed and added a println to the top of the loop to dump the values which quickly highlighted the problem.

I cleaned up the repl checks we were doing into test-round-trip:

(deftest test-round-trip
  (let [nums (range 1 10000)
        round-trip (map #(from-roman (to-roman %)) nums)]
    (is (= nums round-trip))))

That was a fun kata! I wasn’t quite sure how it would work as I’ve never done it before but it wasn’t as bad as I feared.

Full code here.

May 22, 2012 / Alex Miller

Executing Clojure s-expressions on Hadoop

This Thursday (May 24th), we’ll have our monthly Clojure lunch club and David McNeil from Revelytix will be talking about working with Clojure and Hadoop.

Brief description:

This informal talk will describe an approach for running queries as Hadoop Map/Reduce jobs from Clojure. The talk will cover:

  • representing queries as s-expressions in Clojure
  • brief introduction to the Cascading library
  • compiling s-expressions into Cascading flows
  • storing semantic data in Hadoop

The Clojure lunch club meets on the 4th Thursday of the month at 11:30 am in the Revelytix offices.  The office is located at 680 Craig Rd, Suite 106, Creve Coeur 63141.  Lunch is provided!

October 18, 2011 / Alex Miller

“Concurrent Stream Processing” this month

David McNeil will be doing an early run of his talk “Concurrent Stream Processing” at our next Clojure club meeting. David will be presenting this talk next month at the Clojure/conj and Alex Miller will be doing a version of it at Devoxx in Belgium.

It’s a great overview of some of the interesting things done at Revelytix in building a stream-processing query engine and how Clojure has enabled that work. Topics include: how a query engine works, buffering to disk with memory-mapped files (some Java), representing data as s-expressions, and some real world Clojure use.

Meeting: Thursday, Oct. 20th, 2011 at 11:30 am
Location: 1099 Milwaukee, Kirkwood, MO 63122 – Room 50 in basement

Pizza will be provided!

April 27, 2011 / Alex Miller

Clojure Club April meeting

The April meeting of the Clojure Club will be held Thursday, April 28th at 11:30 am at the usual location (1099 Milwaukee, room 50 in the basement).

Nate Young will be talking about some code he’s been writing to implement regex within Clojure. [No snarky comments about Clojure already supporting regex are required.]

Hope to see you there!

January 26, 2011 / Alex Miller

Clojure Club January meeting

The Clojure Club January meeting will be Thursday Jan. 26th from 11:30 am to 12:30 pm (well we usually go till 1 or so) at the Revelytix offices. Pizza or other such lunch will be provided.

Two topics for discussion this month:

  • Jeff Sigmon – a small app that scrapes a website with enlive and outputs text to speech using the MARY TTS Java library
  • Dave McNeil – will show some interesting design aspects of an RDF library that starts from core data structures and decorates abstractions over the top to add features

Hope to see you there!

September 20, 2010 / Alex Miller

Clojure Club 2nd meeting

The second meeting of the Clojure club will be this Thursday, Sept. 23rd at 11:30 am at the Revelytix offices in Kirkwood. Food will be provided.

Last month we did a brief intro to Clojure and talked about various things to do at our meetings. One of the first things we plan to do starting this month is work through a Clojure problem as a group, discovering how to work from problem statement to tests and code.

Hope you can join us!

Follow

Get every new post delivered to your Inbox.