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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
