是否可以重写以避免stackoverflow

Question

我知道这不是惯用的clojure。在现实世界中，我会使用向量。但是，只是好奇，有没有一种方法可以让add-node在不堆叠的情况下工作？例如，也许通过某种方式更改列表中的最后一个节点？

(defrecord ListNode [value next])
(defn add-node [^ListNode curr v]
(if curr
(assoc curr :next (add-node (:next curr) v))
(ListNode. v nil)))
//stackoverflow!
(def result
(loop [l nil i 0]
(if (< i 100000)
(recur (add-node l i) (inc i))
l)))

Answer 1

Clojure的方法是反向构建一个常规列表，将新元素添加到列表的头部。这样，所有操作都只影响(新的(头节点，而不需要消耗堆栈。然后，在最后，您只需反转(单链表(：

(dotest
(let [result-1 (loop [cum nil
val 0]
(if (< val 100000)
(recur
(cons val cum)
(inc val))
cum))
result-2 (reverse result-1)]
(is= (take 10 result-1)
[99999 99998 99997 99996 99995 99994 99993 99992 99991 99990])
(is= (take 10 result-2)
[0 1 2 3 4 5 6 7 8 9])))

如果真的，真的想要，如果你想要的话，你可以使用ListNode结构来重新转换它(但是，为什么？(。

---

话虽如此，如果你想按顺序构建列表，而不需要反转任何东西，只需使用Java LinkedList:

(ns xxx
(:import [java.util LinkedList]))
(dotest
(let [linked-list  (LinkedList.) ]
(dotimes [i 100000]
(.add linked-list i) )
(is= (take 10 linked-list)
[0 1 2 3 4 5 6 7 8 9])
(is= (take-last 10 linked-list)
[ 99990 99991 99992 99993 99994 99995 99996 99997 99998 99999 ] ) ))

你也可以列出一个懒惰的清单。我最喜欢的方法是使用lazy-cons:

(ns tst.demo.core
(:use demo.core tupelo.core tupelo.test))
(defn lazy-nodes
[value limit]
(when (< value limit )
(lazy-cons value (lazy-nodes (inc value) limit)) ))
(dotest
(let [result (lazy-nodes 0 100000)]
(is= (take 10 result)
[ 0 1 2 3 4 5 6 7 8 9] )
(is= (take-last 10 result)
[ 99990 99991 99992 99993 99994 99995 99996 99997 99998 99999 ] ) ))

Answer 2

策略是以相反的顺序收集列表节点，然后自下而上重建列表。可能是这样的：

(defn add-node [^ListNode curr v]
(loop [nodes () curr curr]
(if curr
(recur (cons curr nodes) (:next curr))
(reduce (fn [acc n] (assoc n :next acc))
(ListNode. v nil)
nodes))))
user> (add-node (ListNode. 1 (ListNode. 2 nil)) 100)
;;=> #user.ListNode{:value 1, :next #user.ListNode{:value 2, :next #user.ListNode{:value 100, :next nil}}}

recur部分"反转"列表，而reduce则将累积值(从新节点开始("附加"到下一个，从而获得相同的结构。

现在你的函数不会导致stackoverflow(尝试打印结果仍然会导致它，但还有另一个原因：地图太深了，无法打印(

但对，这只对教育有益(

Answer 3

您似乎缺少将列表定义为代数数据类型list x = (x, list x) | nil的关键功能

这个定义的意义在于它的递归性，对吧？因此，使用这个定义，如果您想将项x添加到现有的xs列表中，只需执行new-list = (x, list x)即可。

在代码中，add-node函数应定义为：

(defn add-node [^ListNode xs x] (ListNode x xs))

现在，如果你想向这个列表中添加大量的项目，你不会有堆栈溢出，但由于递归定义，你的列表将是一个LIFO风格的列表。您插入的最后一个项目将是您看到的第一个项目。它是O(1(得到头部，O(n(得到其他任何东西。这是定义所暗示的。在您当前的add-node定义中，每个插入都是O(n(，这可能意味着您使用了错误的数据结构。

这是函数式编程中非常常见的习惯用法，如lisps(cons-lists(和haskell。如果您想扭转列表，那么编写反向操作是非常琐碎的。然而，如果是这样的话，您可能希望同时使用不同的数据结构，例如clojure的vector或差异列表(请参阅Bill Burdick的精彩回答(