Quicksort

[nahiluhmot]

Hello all,
I'm very new to clojure, so to familiarize myself I decided to try to
implement the quicksort. My code looks like this:

(defn qsort
([] nil)
([list]
(let [piv (peek list)
f-half (filter (fn [n] (<= n piv)) (pop list))
s-half (filter (fn [n] (> n piv)) (pop list))]
(concat (qsort f-half) (cons piv (qsort s-half))))))

This looks logical to me, but when I try to run it, I get the
following exception:

user=> (qsort [4 1 3])
java.lang.ClassCastException: clojure.lang.LazySeq cannot be cast to
clojure.lang.IPersistentStack (NO_SOURCE_FILE:0)

I have tried wrapping a doall around the filter functions, and I get
the same error.

Thanks in advance!

[Nathan Sorenson]

Couple of things to watch out for, Clojure doesn't pattern match on the args in the way you seem to be expecting, so this will blow the stack (i.e. calling qsort with the empty list won't call the 0-argument method you have there.)

The error you're running into is that pop/peek isn't defined for lazy sequences. doall will force your lazy-sequence, but it's still of type LazySeq:

>(type (lazy-seq [1 2 3]))

clojure.lang.LazySeq

So putting the base-case into an if/else branch, and switching pop/peek for rest/first would look like so:

(defn qsort 

  ([list] 

     (if (seq list)

       (let [piv (first list) 

             f-half (filter (fn [n] (<= n piv)) (rest list)) 

             s-half (filter (fn [n] (>  n piv)) (rest list))] 

         (concat (qsort f-half) (cons piv (qsort s-half))))

       nil)))

[Nathan Sorenson]

Obviously the example of doall not being up to the task should read:

scratch> (type (doall (lazy-seq [1 2 3])))

clojure.lang.LazySeq