Infinity: Easier Than You Think. Infinitely.

Spaghettified musings on software

  • May 2010
    S M T W T F S
    « Jan   Jun »
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  

Does Groovy Know You Are Seeing Clojure?

Posted by gdjsky01 on 2010/05/01

With all due credit to Venkat Subramaniam for the paraphrased title of this posting.

I’m not sure exactly when I decided to learn Clojure. I know I’d heard about it as one of four JVM languages with a lot of buzz in 2009 (yes I know there are other JVM languages). At the time of  ‘discovery’, I was in New Orleans at last October’s (2009) SpringOne/2GX swooning with others over our love of Groovy and all things Groovy. The other three I am thinking of are a Ruby clone JRuby, a weird language called Scala, and Clojure. Yes I am aware calling Scala weird is a bit of the pot and tea kettle syndrome but I find Scala to be the C or APL syntax of the JVM languages. All things considered, in my not so humble opinion, there is no other language I would rather code with than Groovy. It’s just the most natural and powerful progression from Java. Maybe that is controversial, but since this is my blog, it’s my opinion.

Now I am a bit of a language junkie and always have been since I was a tyke in 1979 coding on a TRS-80 Model 1 in Basic and Z-80 assembler. I’ve toyed around with, or coded for a good living in, Z-80, 6502, 68000, x86 assembler, Modula 2, Pascal, Forth, C, C++, Java, Ruby ,Groovy, and now Scheme (a tad) and Clojure. Pretty decent list if I do say so myself. Oh and sitting on my bookshelf is a book on Erlang. However I can say with some certainty: In the intervening 30 years since starting out on a TRS-80 Model 1 nothing has been more difficult in terms of solving even the most trivial of problems than learning Clojure.

Of course there is a good chance this has nothing to really do with Clojure at all. It is really Functional Programming (FP) that is giving me fits. After all, if you take away FP, learning Clojure is just learning Lisp (it’s Clojure’s immutable paradigms that differ from Lisp – as far as I can tell). I have been doing pretty well with the “Little Schemer” for learning a dialect of Lisp. But alas, I don’t find that translates into Clojure. Not sure why. For two months, I’ve been reading blogs, reading MEAPs (Clojure in Action and The Joy of Clojure), and reading source.

At first reading Clojure was the problem (and still is to some extent – reading is not writing) as I had no Lisp or Scheme exposure. The only thing I knew about Lisp was the oft repeated refrain that truly great programmers know Lisp is the secret weapon. Like Paul Graham’s Beating the Averages post. Did I believe it? Do I believe it? I suppose I did believe it and I did not care. There was much more money in Java and C++ than Lisp, so why worry about that I am using so-called second rate languages. (A strawman there but you know what I mean.) I am in this profession to make a living, not impress people with the tools I use.

Do I still believe it? Umm… not right this minute. I am having such a heck of a time coding anything beyond Hello World in Clojure I have begun to wonder if only certain level guru’s can ever ‘get it’. Notice I am not making a distinction between coding in Clojure/Lisp and Functional Programming. The reason is as far as I can ascertain in the Clojure world, they go hand-in-hand. Imperative Programming in Clojure is really fighting the language. So one could say I really bit off way more than maybe I should have. On one hand I decided to learn something about Functional Programming and on the other decided Clojure would facilitate that because you are virtually forced to immerse yourself in FP from the start. Or maybe it was the other way around. Maybe it was Clojure making me discover FP.

Either way I took on two totally unknowns and for two months now I have paid a mental price for it. It has been really frustrating. The simplest imperative programming solutions don’t even give me a hint, a clue, as to an approach of how to solve the same problem in Clojure/FP without a lot of mutable state. Take a simple problem we use at my employer to get a small perspective on possible new hires and how they approach solving problems in Java: This problem is to take a vector of intra-day stock prices for some particular stock (numbers) and determine the maximum profit you could have made buying that day and selling that day. Simple stuff in an imperative language. You simply keep track of the minimum value, the profit, and replace the minimum whenever the next value is less the current minimum.

Well my dear readers… I could not for the life of me figure that out in Clojure/FP. Now remember I’ve not written ANY Clojure or done any FP. Just read about it. This was my ‘do something real’, sort of  a Hello World.

“What’s the big deal?”, all you expert FP’ers (or even novice) FP’ers are saying. Yeah thats the thing, I have no idea what the big deal is. Just could not find the approach. Or the correct higher order function(s) to use. Just could not figure out how to keep track of two things (minimum and profit) without a mutable variable someplace. Frankly, maybe at age 51 you can not teach an old dog of 30 years, this new trick.

To this day I did not really figure it out on my own. Instead I casually mentioned the challenge to my local friendly Scala enthusiast. He took up the cause and came up with something like this

A.foldLeft((Math.MAX_INT,0))((s,curr)=>(Math.min(curr,s._1),Math.max(curr-s._1,s._2)))._2

Now you begin to see how stupid I was feeling. Not only did he solve the problem, he solved it in a line of code that fit in a tweet on Twitter with room to spare.

The tuple was what gave me the idea of using a structure. And I guess I did solve it. It’s not pretty, and it’s way more than one line, but it appears to pass my tests.


(def closing-prices '(23 24 21 23 45 33 22 1 33 4 2 23)
;;(def no-profit-closing-prices '(23 21 20 19 18 17 16 15 14 13 1 0))
;;(def closing-prices '(23 24 20 19 18 17 16 15 14 13 1 0))

(defstruct values :min :profit)

(defn calc-profit [current-values next-val]
    ;;(println (current-values :min) (current-values :profit) next-val)
    (let [mini (min (:min current-values) next-val)
          profit (max (:profit current-values) (- next-val mini))]
        (assoc current-values :min mini :profit profit)))

(defn find-profit [coll]
    (let [v (struct-map values :min (Integer/MAX_VALUE) :profit -1)]
        (reduce calc-profit v coll)))

(:profit (find-profit closing-prices))

Of course my greatest fear is you’ll post a comment showing me a single line of Clojure that does the trick. 😉

So why subject myself to this self-inflicted torture?

  1. I believe Rich Hickey is right. More cores not higher clock frequencies are the near future. FP is really a boon in concurrent coding as you can more easily reason about the code’s behavior with multiple threads.
  2. I almost never see a really great object hierarchy in OO languages. They start out small and clean and grow to crap and cruft. Not in 20 years of OOP have a seen a really great object hierarchy (yes a logical fallacy but still true in my case). Indeed most of us now use composition, aggregation, and delegation, not inheritance. In FP you have to use composition. It is all about composing functions from other functions.
  3. Its a challenge. Different way of thinking. And maybe secretly I want to join that elite illuminati of Lisp engineers…

But Groovy is soooo much easier! Will Clojure win my heart…

Advertisements

31 Responses to “Does Groovy Know You Are Seeing Clojure?”

  1. Lee said

    That was a fun kata for Clojure, here’s the shortest I could come up with on short notice:

    (def prices '(23 24 21 23 45 33 22 1 33 4 2 23))
    
    (defn prof [[p & r]] (if (boolean r) (cons (- (apply max r) p) [(prof r)]) -1))
    (apply max (flatten (prof prices)))
    

    This assumes you’re using Clojure 1.2 which includes ‘flatten’ in the core functions. Short enough to fit into a tweet 🙂 (assuming you take out the declaration of prices)

  2. […] This post was mentioned on Twitter by groovyblogs.org, Jeff Gortatowsky. Jeff Gortatowsky said: Does #Groovy Know You Are Seeing #Clojure? http://bit.ly/aRMIMz […]

  3. Eric B. said

    I like it. Wanted to try my hand at it too. Here’s some groovy to do the same thing:

    import static java.lang.Integer.*
    import static java.lang.Math.*

    // Test Data {{{
    def tests = [
    [23, 24, 21, 23, 45, 33, 22, 1, 33, 4, 2, 23],
    [23, 21, 20, 19, 18, 17, 16, 15, 14, 13, 1, 0],
    [23, 24, 20, 1, 18, 17, 16, 15, 14, 13, 1, 0],
    []
    ]

    def results = [
    32,
    -1,
    17,
    -1
    ]
    // }}}

    tests.eachWithIndex { A, index ->
    def curr = MAX_VALUE
    def prof = -1
    A.each {
    curr = curr < it ? curr : it
    if(curr != it) {
    prof = it - curr < prof ? prof : it - curr
    }
    }
    println "$A - max prof: ${prof}"
    assert results[index] == prof
    }

    // for jEdit's ScriptEngine
    SCRIPTVALUE = ""
    // jEdit - A Programmer's Text Editor (www.jedit.org) {{{
    // ::collapseFolds=1:folding=explicit:indentSize=3:maxLineLen=120:mode=groovy:noTabs=true:tabSize=3::
    // }}}

    • gdjsky01 said

      My groovy solution was on my work computer. I’ll post it as soon as I have it. Thanks for reading this and your input!

  4. Jens said

    Based on the Scala solution, I first wrote a Groovy version to verify I got it.

    def CP = [23, 24, 21, 23, 45, 33, 22, 1, 33, 4, 2, 23]
    CP.inject( [min:Integer.MAX_VALUE, profit:0] ) {state, price ->
        [min: Math.min(state.min, price), profit:Math.max(price - state.min, state.profit)]
    }.profit
    -------------------
    Result: 32
    

    Then I wrote the same solution in Erlang

    Erlang R13B03 (erts-5.7.4) [smp:2:2] [rq:2] [async-threads:0]
    Eshell V5.7.4  (abort with ^G)
    1> CP = [23, 24, 21, 23, 45, 33, 22, 1, 33, 4, 2, 23].
    [23,24,21,23,45,33,22,1,33,4,2,23]
    3> element(2, lists:foldl(fun(Price, {Min,Profit}) -> {erlang:min(Min,Price), erlang:max(Price - Min, Profit)} end, {999999, 0}, CP)).
    32
    

    I still believe your Clojure solution can be simplified. Although you convinced me of staying away from Clojure, for yet another while 😉

    • gdjsky01 said

      My intent was really to vent. Would it not be true however if you can think in erlang, you are already over the FP hurdle? If so, Clojure probably is not as big a leap as you think. Erlang is probably my next target, but not for a while. One thing at a time (not that I followed that advice!) Thanks for the input!

    • Eric B. said

      Nice! I didn’t know about the inject method – learn something new every day.

  5. I thought I would represent the Clojure one-liner here and give your problem a shot:


    (apply max (map (fn [[x y]] (- y x)) (partition 2 1 [23 24 21 23 45 33 22 1 33 4 2 23])))

    What’s going on there is the “partition” function breaks the input vector into sub-sequences of 2 elements each, offset by 1. So, the vector [1 2 3] would become [[1 2] [2 3]]. Then, I map each pair to its “difference”, and then select the maximum difference.

    I may have misunderstood the problem, but the above code gives “32” like your other examples.

    Anyways, I hope this sheds some light! I went through a Scala phase but have found Clojure much more fun, and about as “powerful,” but in different (and, IMHO, more important) ways. Happy coding, and thanks for the article!

    • gdjsky01 said

      32 is the correct. Buying at 1 and selling at 33. Then there is the no profit test where the opening price is the highest (profit 0) and of course empty list (like the market was closed). Thanks for the comment!

      • Meikel said

        Hmm. However the partition above is not the same as your reduced min.

        Here my try:

        (def closing-prices [23 24 21 23 45 33 22 1 33 4 2 23])
        
        (defn find-profit
          [coll]
          (apply max (map #(- %1 %2) coll (reductions min coll))))
        

        Reductions is in core in the master repo. Otherwise it can be found in clojure.contrib.seq-utils.

      • Meikel said

        Ah. Mac had the same solution. And he avoided the anon-fn. 🙂

  6. Mac said

    try. reductions is in clojure.contrib as of 1.1, but will be part
    of core in 1.2. You can use it by doing (use ‘clojure.contrib.seq-utils)

    (reduce max (map – closing-prices (reductions min closing-prices)))

    I’m using reductions to find the min value at each position. I used your
    closing-prices def. the output looks like this

    user=> closing-prices
    (23 24 21 23 45 33 22 1 33 4 2 23)
    user=> (reductions min closing-prices)
    (23 23 21 21 21 21 21 1 1 1 1 1)

    then I map it with a – to see the max possible profit, then
    used the reduce max to find the max profit.

    • gdjsky01 said

      Okay. Let me run that and figure it out. The answer for the input should be 32 (buy at 1 sell at 33). I feel good I solved it. But not great about the solution! 🙂 Thanks for dropping by!

      • Mac said

        results follow

        user=> (def closing-prices ‘(23 24 21 23 45 33 22 1 33 4 2 23))
        #’user/closing-prices
        user=> (reduce max (map – closing-prices (reductions min closing-prices)))
        32
        user=> (def no-profit-closing-prices ‘(23 21 20 19 18 17 16 15 14 13 1 0))
        #’user/no-profit-closing-prices
        user=> (reduce max (map – no-profit-closing-prices (reductions min no-profit-closing-prices)))
        0

  7. Nguyễn Tuấn Anh said

    Hi, this is my Clojure version. I don’t know if it’s good or not since I’m a Clojure newbie, but I think it avoids using Integer/MAX_VALUE, which can be a problem for larger integers.


    (defn max-profit-if-buy-first [coll]
    (- (apply max coll) (first coll)))

    (defn max-profit [coll]
    (apply max (map #(max-profit-if-buy-first (drop % coll))
    (range (count coll)))))

    It can be made shorter, but then not very readable

    (defn max-profit [coll]
    (apply max (map #(- (apply max (drop % coll))
    (nth coll %))
    (range (count coll)))))

    • gdjsky01 said

      Thank you for the comment. I’ll look it over. Hopefully lightbulbs will go on someday if I keep at it! 🙂

  8. Mac’s solution is nice; I just wanted to mention one other thing. A nice thing about clojure is the -> and ->> macros for converting inside-out forms into left-to-right (or top-to-bottom) ones.

    One way to view this problem is in three steps: (1) find the lowest price at each point (2) find the possible profit at each point, (3) take the max of #2.

    http://gist.github.com/387372 shows how this looks, indented idiomatically and with comments. It fits in a tweet but that’s just golfing, and I wouldn’t write it that way.

    Seeding the solution with a sentinel constant (e.g. Integer/MAX_VALUE) or prefixing functions with class-looking things (e.g. Math.max) seems very ugly to me.

    • gdjsky01 said

      Yeah the thing about fitting it in a tweet was just my friend showing off. He too agreed it becomes unreadable. But it does show the expressiveness of languages like scala and clojure that so much can be done in so little.

  9. Frode St said

    I think your solution is good and can be just as short as the Scala version. I have used a vector instead of a map to hold the accumulator for the reduce function:


    (defn calc-profit [prices]
    (first (reduce (fn [[delta low] price] [(max delta (- price low)) (min price low)])
    [0 Integer/MAX_VALUE] prices)))

  10. […] Does Groovy Know You Are Seeing Clojure? « Infinity: Easier Than You Think. Infinitely. […]

  11. gdjsky01 said

    Thanks everyone for the comments. I’ll read and learn. Sentinel value is ugly. IMO defense, had this been a real stock tracking problem, I think a stock price in the 2 billions would have or should have been flagged as an error. But I am just rationalizing. As you all can see, it’s not about the problem. Its not about the steps that solve the problem. It’s about mapping the steps to FP and to Clojure’s available higher order functions. That is the Guru part. 🙂 Cheers!

    • James Iry said

      The sentinel can be removed by using Option and it still fits in a tweet.

      prices.foldLeft((prices.headOption, 0)){(s, curr) => (Some(Math.min(curr, s._1.get)), Math.max(curr – s._1.get, s._2))}._2

      This is one of the odd examples where you can use Option#get and strictly local reasoning shows that you’re guaranteed to not get an exception.

      But all that tupling stuff is a bit hard to follow. Pattern deconstruction gives you much better self documentation.

      prices.foldLeft((prices.headOption, 0)){case ((min, profit), curr) => (Some(Math.min(curr, min.get)), Math.max(curr – min.get, profit))}._2

      That just barely fits into a tweet.

      The Clojure solutions using “reductions” are pretty nice, too, albeit at some small constant multiple of extra runtime work. I don’t think the Scala standard library has that (or it’s Haskell cousins scanl/scanl1) just yet but it’s not hard to write. The advantage of “reductions” style approach is that it’s more generally useful. With only small changes it can answer the challenge “give me the maximum profit that could have been taken at each point in the day.”

      To the meta level that the post is really about: how do you learn to “think” this way. The answer is that there’s no quick and easy path. It takes practice. It’s a different set of mental muscles. They need to be trained and exercised.

      Simple imperative loops over lists are most directly modeled with a fold (or reduce or whatever your language calls it). So start by mentally translating. Just as with a foreign language it will be unnatural at first but more natural over time. Then learn to recognize when higher level concepts like map and bind (flatMap in Scala, >>= in Haskell, and mapcat in Clojure) apply.

      Once you master functional thinking you’ll actually realize that imperative thinking is harder because keeping track of mutable variables requires more mental gymnastics. You’ll also come to appreciate that functions like “reductions” are so reusable and composable that you don’t have to retype boilerplate loops over and over again. Give it time. Practice it. Don’t let yourself get too frustrated with early challenges.

      • gdjsky01 said

        Thanks for your thoughtful reply. Essentially yes, that is what the post is really about. Drats… here I was hoping there was a pill that would instantly make me start thinking FP. “There’s an app for that..” 🙂 Now… what is the next real world, but small enough to experiment with, example I should tackle???

  12. Tom said

    Great post. I echo you’re thoughts. I use Groovy at work and have been studying Clojure. Without question many programmers won’t either be interested or capable of using Clojure. Not because it’s a bad language but because it’s so different. I see it as a tool to use someday for some particular problems.

  13. Jabba said

    I found Prolog rather than Lisp the language that required the greatest paradigm shift from traditional languages.

  14. […] ran across an interesting blog post the other day from Jeff Gortatowsky. He has been trying to learn clojure and was having a hard time […]

  15. gdjsky01 said

    Interesting. Some of these solutions are wrong. (Yes I have been away and busy 😉 )
    For example using the same data set but with one switch, 33 swapped with 23, some solutions are wrong. They answer is still buy at 1 sell at 33. Try this:
    (23 24 21 23 45 33 22 1 4 2 23 33)

  16. I am totally agree with your oppinion.this blog post is very encouraging to people who want to know these topics.

  17. […] Does Groovy Know You Are Seeing Clojure? – A real world story of learning Clojure, the Functional Programming language on top of the JVM. I can wholeheartly agree with the sentence “In the intervening 30 years since starting out on a TRS-80 Model 1 nothing has been more difficult in terms of solving even the most trivial of problems than learning Clojure.”, but in my case, it has been a little more than 15 years of real experience. After a year trying to “get” Clojure, I deferred it for more productive work. […]

  18. John said

    From my point of view, I’m not really sure I want to give Lisp like languages a chance. I feel functional enough with Groovy/Ruby 🙂

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

 
%d bloggers like this: