clojure中的插入排序抛出StackOverFlow错误

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))) 

抛出一个堆栈溢出错误。我在这里做错了什么？

Answer 1

同样的问题与Recursive function causing a stack overflow。 Concat建立了一堆嵌套的懒序列，例如（concat（concat（concat ...）））而没有做任何实际的工作，然后当你强制第一个元素时，所有的concat都必须立刻解决，叠加。

Answer 2

您的reduce每次创建一个新列表。

我的实现：

(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

正如主要答案所示，列表concat是罪犯。呼唤“DOALL”，与列表作为输入...将导致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)) 

别急......是序列还是懒惰？

上面的代码有趣的是，下面的代码表明这个序列确实还是很懒！

;;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)) 

所以，如果名单仍然懒惰，那么为什么不使用的doall的修复什么？

“doall”函数不适合返回“非懒惰”列表，而是它确保它返回的列表将通过完整遍历进行评估。

因此，问题的实质是多重函数调用，懒惰无疑与原始问题中代码的这一方面有关，但它不是溢出的“主要”来源。