If you run out stack in Scheme the code is not properly tail recursive. Who care when it blows?
On Thu, Dec 1, 2011 at 12: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 -- 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
