Tassilo Horn <tass...@member.fsf.org> writes:
>> I've seen people solve these issues by forcing the intermediate seqs,
>> but that doesn't work well for a lazy situation such as this.
>
> Indeed, putting a doall around the filter and remove seems to prevent
> the stack overflow.
A better solution seems to be to use a sequence comprehension:
--8<---------------cut here---------------start------------->8---
(defn sort-parts
"Lazy, tail-recursive, incremental quicksort. Works against
and creates partitions based on the pivot, defined as 'work'."
[work]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [smaller? #(< % pivot)]
(recur (list*
(for [x xs :when (smaller? x)] x)
pivot
(for [x xs :when ((complement smaller?) x)] x)
parts)))
(when-let [[x & parts] parts]
(cons x (sort-parts parts)))))))
(defn qsort [xs]
(sort-parts (list xs)))
--8<---------------cut here---------------end--------------->8---
It also seems to perform a bit better than the original solution.
However, I cannot see any big difference in speed compared to my simple
straight-forward solution:
--8<---------------cut here---------------start------------->8---
(defn qsort2 [xs]
(lazy-seq
(when (seq xs)
(let [[p & r] xs]
(concat (qsort (for [y r :when (< y p)] y))
[p]
(qsort (for [y r :when (>= y p)] y)))))))
--8<---------------cut here---------------end--------------->8---
Bye,
Tassilo
--
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
