Quoth john.holland on Sweetmorn, the 44th of The Aftermath:
> It seems to me that as general solutions to stack overflow,
> trampoline and recur are very valuable. I had gotten the mistaken
> idea that Scheme was somehow immune to the problem.
Trampoline and recur are a poor man's tail-call-optimi
On Dec 2, 8:13 pm, "john.holland" wrote:
> Thanks for all the replies. It seems to me that as general solutions to
> stack overflow, trampoline and recur are
> very valuable. I had gotten the mistaken idea that Scheme was somehow
> immune to the problem.
> My experiments in Scheme seemed to ge
Thanks for all the replies. It seems to me that as general solutions to
stack overflow, trampoline and recur are
very valuable. I had gotten the mistaken idea that Scheme was somehow
immune to the problem.
My experiments in Scheme seemed to get to higher amounts of recursion
before blowing up
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 wi
Here's the simplest way to adapt your code so that it won't blow the
stack. Just shuffle the input list first:
(defn quicksort [l]
(letfn [(qsort [[pivot & xs]]
(when pivot
(let [smaller #(< % pivot)]
(lazy-cat (qsort (filter smaller xs))
There are versions of Quicksort that don't use recursive function calls.
Instead they simulate recursion by maintaining a stack of indices. (Search
the web for "quicksort without recursion.") You could do that in Clojure
with loop/recur.
-S
--
You received this message because you are subscr
Try increasing the JVM's stack size with -Xss.
--
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 u
I didn't mean the response to sound overly curt. You can set the stack size
on JVM.
But the point is, that quick sort is simply wrong if you do not want to
grow the stack, whether in Scheme or in Clojure.
On Thu, Dec 1, 2011 at 5:07 PM, David Nolen wrote:
> If you run out stack in Scheme the co
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 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
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. S
10 matches
Mail list logo
