Hi, the Scheme version of quicksort is not tail-recursive since append is called on the return value of the recursive calls. Thus, also in Scheme this eats up your stack. That your Scheme code can sort larger sequences simple means that your Scheme implementation has a larger stack than the JVM with standard settings. Basically, the only difference between Scheme and Clojure with respect to tail-recursion is that Scheme automatically optimizes the recursive call when it appears in a tail-call position whereas in Clojure you have to explicitly call recur (or trampoline for mutual recursion) if you want tail-call optimization.
Since quicksort requires two recursive calls which then have to be combined it is not completely trivial to implement it in a tail- recursive, i.e. iterative, fashion. There is a general method which can be applied, namely continuation passing style (CPS), but it might look a little odd if you haven't seen it before. Basically, you use a variable holding a chain of closures which resemble the stack. I found a rather nice exposition in this blog post: http://www.enrico-franchi.org/2011/09/clojure-quicksort-in-continuation.html Cheers, Nils On Dec 1, 6:09 pm, "john.holland" <jbholl...@gmail.com> wrote: > I was studying clojure for a while, and took a break to work on SICP in > scheme. I found that they do numerous things that are against advice in > Clojure having to do with the tail recursion. > I got to thinking about that Clojure recur/loop stuff and wondered how you > would do a quicksort with it. So I went to rosetta code and looked at what > they had for scheme and for clojure. > > In scheme I can do a quicksort which makes two calls to itself and it can > scale pretty high before running out of RAM. I went up to 10000 sorting > from worst (reversed) order to forward order. I do get > stack overflows beyond that though. > > In clojure, the same algorithm produces the dreaded StackOverflow after > 1000 values. > I tried giving the JVM a gig of RAM, no help. > > Below are the (trvial) procedures. > > I understand that the advice in clojure is to use loop/recur etc, however, > a big part of the charm for me of something like scheme is that I can write > code that is a straightforward statement of a mathematical approach to the > problem. > > Although quicksort is really simple, the idea of doing it with loop/recur > baffles me. > > After a while with the scheme stuff clojure seems very complex and this, > which seems like a fundamental issue, is not going well for it. > > Can anyone post a quicksort that doesn't give stack overflows in clojure? > > John > > ====scheme quicksort============================================ > > (define (quicksort l) > (if (null? l) > '() > (append (quicksort (filter (lambda (x) (> (car l) x)) (cdr l)) ) > (list (car l)) > (quicksort (filter (lambda (x) (< (car l) x)) (cdr l)) )))) > > =================scheme utility to make data sets================ > (define (nums x) (if (< x 0) '() (cons x (nums (- x 1))))) > > ======================scheme call================= > (quicksort (nums 10000)) > > ===============================clojure quicksort==================== > (defn qsort [[pivot & xs]] > (when pivot > (let [smaller #(< % pivot)] > (lazy-cat (qsort (filter smaller xs)) > [pivot] > (qsort (remove smaller xs)))))) > > =================clojure utility to make data sets================ > (def nums (fn [lim] (loop [limx lim acc []] (if (< limx 0) acc (recur (- > limx 1) (cons limx acc)) )))) > > ====clojure call================================================== > (quicksort (nums 10000)) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
