Insert sort in clojure throws StackOverFlow error

Question

(defn insert [sk] (let [spl (split-with #(< % k) s)] (concat (first spl) (list k) (last spl)))) (defn insert-sort [s] (reduce (fn [sk] (insert sk)) '() s)) (insert-sort (reverse (range 5000))) 

throws a stack on a stream error. What am I doing wrong here?

Answer 1

Same problem as with Recursive function causing stack overflow . Concat creates a bunch of nested lazy sequences such as (concat (concat (concat (concat ...))) without any actual work, and then when you force the first element, all concat must be resolved immediately, blowing the stack.

Answer 2

Your reduce creates a new list every time.

My implementation:

 (defn- insert [el seq] (if (empty? seq) (cons el seq) (if (< el (first seq)) (cons el seq) (cons (first seq) (insert el (rest seq)))))) (defn insertion-sort ([seq sorted] (if (empty? seq) sorted (recur (rest seq) (insert (first seq) sorted)))) ([seq] (insertion-sort seq nil))) 

Answer 3

As follows from the main answer, the concat list is an intruder. Calling "doall", with this list as input ... will result in ISeq:

  ;;insertion sort helper (defn insert [sk] ;;find the insert point (let [spl (split-with #(< % k) s) ret (concat (first spl) (list k) (last spl))] (doall ret))) ;;insertion sort (defn insert-sort [s] (reduce (fn [sk] (insert sk)) '() s)) 

But wait ... Is the sequence still lazy?

The following hacked code, interestingly, indicates that the sequence is really still lazy!

 ;;insertion sort helper (defn insert [sk] ;;find the insert point (let [spl (split-with #(< % k) s) ret (concat (first spl) (list k) (last spl)) ret2 (doall ret) _ (println "final " (.getClass ret2))] ret2)) ;;insertion sort (defn insert-sort [s] (reduce (fn [sk] (insert sk)) '() s)) 

So, if the list is still lazy, then why using doall doesn't fix anything?

The doall function is not guaranteed to return a non-lazy list, but rather, it ensures that the list it returns is evaluated by fully scrolling.

Thus, the essence of the problem lies in calling several functions, laziness is certainly related to this aspect of the code in your original question, but this is not the "primary" source of overflow.