Clojure - (another) StackOverflow with / recur outline

Question

I know this is a recurring question ( here , here , etc.), and I know that the problem is with the creation of lazy sequences, but I do not understand why it fails.

Problem: I wrote a (not very good) quicksort algorithm to sort strings that use loop / recur. But applied to 10,000 elements, I get a StackOverflowError:

(defn qsort [list]
  (loop [[current & todo :as all] [list] sorted []]
    (cond 
       (nil? current) sorted 
       (or (nil? (seq current)) (= (count current) 1)) (recur todo (concat sorted current))
       :else (let [[pivot & rest] current
                  pred #(> (compare pivot %) 0)
                  lt (filter pred rest)
                  gte (remove pred rest)
                  work (list* lt [pivot] gte todo)] 
                (recur work sorted)))))

I used this way:

(defn tlfnum [] (str/join (repeatedly 10 #(rand-int 10))))
(defn tlfbook [n] (repeatedly n #(tlfnum)))
(time (count (qsort (tlfbook 10000))))

And this is part of the stack trace:

  [clojure.lang.LazySeq seq "LazySeq.java" 49]
  [clojure.lang.RT seq "RT.java" 521]
  [clojure.core$seq__4357 invokeStatic "core.clj" 137]
  [clojure.core$concat$fn__4446 invoke "core.clj" 706]
  [clojure.lang.LazySeq sval "LazySeq.java" 40]
  [clojure.lang.LazySeq seq "LazySeq.java" 49]
  [clojure.lang.RT seq "RT.java" 521]
  [clojure.core$seq__4357 invokeStatic "core.clj" 137]]}

As far as I know, loop / recur performs tail call optimization, so the stack is not used (in fact, it is an iterative process written using recursive syntax).

- concat doall concat . ... ?

Answer 1

​​ concat.

(defn concat [x y]
  (lazy-seq
   (let [s (seq x)]
     ,,,))
  )

, : lazy-seq seq. lazy-seq , , . lazy-seq . lazy-seq, ( "" seq), .

(def lz (lazy-seq
         (println "Realizing!")
         '(1 2 3)))

(first lz)
;; prints "realizing"
;; => 1

:

(defn lazy-conj [xs x]
  (lazy-seq
   (println "Realizing" x)
   (conj (seq xs) x)))

, concat, seq a lazy-seq

(def up-to-hundred
  (reduce lazy-conj () (range 100)))

(first up-to-hundred)
;; prints "Realizing 99"
;; prints "Realizing 98"
;; prints "Realizing 97"
;; ...
;; => 99

, , . , "" seq "", seq, seq .. , , , .

(def up-to-ten-thousand
  (reduce lazy-conj () (range 10000)))

(first up-to-ten-thousand)
;;=> java.lang.StackOverflowError

concat. , , (reduce concat ,,,) , (apply concat ,,,) (into () cat ,,,).

filter map . , .

;; without transducers: many intermediate lazy seqs and deep call stacks
(->> my-seq
     (map foo)
     (filter bar)
     (map baz)
     ,,,)


;; with transducers: seq processed in a single pass
(sequence (comp
           (map foo)
           (filter bar)
           (map baz))
          my-seq)

Answer 2

(, , cat !). , glue Tupelo:

---

concat :

(concat {:a 1} {:b 2} {:c 3} )
;=>   ( [:a 1] [:b 2] [:c 3] )

, , 3 . -2, .

conj :

(conj [1 2] [3 4] )
;=>   [1 2  [3 4] ]

, , [1 2 3 4] , .

, , , , , :

; Glue together like collections:
(is (= (glue [ 1 2] '(3 4) [ 5 6] )       [ 1 2 3 4 5 6 ]  ))   ; all sequential (vectors & lists)
(is (= (glue {:a 1} {:b 2} {:c 3} )       {:a 1 :c 3 :b 2} ))   ; all maps
(is (= (glue #{1 2} #{3 4} #{6 5} )      #{ 1 2 6 5 3 4 }  ))   ; all sets
(is (= (glue "I" " like " \a " nap!" )   "I like a nap!"   ))   ; all text (strings & chars)

; If you want to convert to a sorted set or map, just put an empty one first:
(is (= (glue (sorted-map) {:a 1} {:b 2} {:c 3})   {:a 1 :b 2 :c 3} ))
(is (= (glue (sorted-set) #{1 2} #{3 4} #{6 5})  #{ 1 2 3 4 5 6  } ))

, , "", . :

• : ( )
• ( )
• ( )
• : ( )

---

glue concat StackOverflowError. , filter remove keep-if drop-if, :

(defn qsort [list]
  (loop [[current & todo :as all] [list] sorted []]
    (cond
      (nil? current) sorted

      (or (nil? (seq current)) (= (count current) 1))
          (recur todo (glue sorted current))

      :else (let [[pivot & rest] current
                  pred #(> (compare pivot %) 0)
                  lt   (keep-if pred rest)
                  gte  (drop-if pred rest)
                  work (list* lt [pivot] gte todo)]
              (recur work sorted)))))

(defn tlfnum [] (str/join (repeatedly 10 #(rand-int 10))))
(defn tlfbook [n] (repeatedly n #(tlfnum)))
(def result
  (time (count (qsort (tlfbook 10000)))))

-------------------------------------
   Clojure 1.8.0    Java 1.8.0_111
-------------------------------------
"Elapsed time: 1377.321118 msecs"
result => 10000