Insertion sort in clojure throws StackOverFlow error

Question

(defn insert [s k]
    (let [spl (split-with #(< % k) s)]
       (concat (first spl) (list k) (last spl))))

(defn insert-sort [s]
    (reduce (fn [s k] (insert s k)) '() s))

(insert-sort (reverse (range 5000)))

throws a stack over flow error. What am I doing wrong here?

Bowshot

interesting on my repl it dies as early as list size 891 – Theurgy

Answer 1

Same issue as with Recursive function causing a stack overflow. Concat builds up a bunch of nested lazy sequences like (concat (concat (concat ...))) without doing any actual work, and then when you force the first element all the concats must get resolved at once, blowing the stack.

Whitefly

Answer 2

Your reduce creates new list each 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)))

Officinal

I don't quite understand. If I replace your insert with mine, I still get a stack over flow error. (defn insert [s k] (let [spl (split-with #(< % k) s)] (concat (first spl) (list k) (last spl)))) (defn insertion-sort ([seq sorted] (if (empty? seq) sorted (recur (rest seq) (insert sorted (first seq) )))) ([seq] (insertion-sort seq nil))) – Bowshot

yes, but you still hit reduce each time. I am using tail recursion calls. see recur clojuredocs.org/clojure_core/clojure.core/recur – Officinal

Answer 3

As the main answer suggests, the list concat is the offender. Calling "doall", with that list as input... will result in an ISeq :

   ;;insertion sort helper
    (defn insert [s k]
        ;;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 [s k] (insert s k)) '() s))

But wait... Is the sequence still lazy ?

The following hack of the above code, interestingly, indicates that the sequence is indeed still lazy !

;;insertion sort helper
(defn insert [s k]
    ;;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 [s k] (insert s k)) '() s))

So, if the list is still lazy, then why does the use of doall fix anything ?

The "doall" function is not gauranteed to return a "non lazy" list, but rather, it gaurantees that the list which it DOES return will have been evaluated by a full walk through through.

Thus, the essence of the problem is the multiple function calls, the laziness is certainly related to this aspect of the code in your original question, but it is not the "primary" source of the overflow.

Theurgy