Possible to rewrite this to avoid stackoverflow?

Question

I know this isn't idiomatic clojure. In the real world, I'd use a vector. But, just curious, is there a way to make add-node work without stackoverflowing? Like for example, perhaps by somehow mutating the last node in the list?

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

Alan Thompson · Answer 1 · 2018-08-02T19:52:18.160

The Clojure way of doing it would be to construct a regular list in reverse, adding the new element to the head of the list. This way, all of your operations only affect the (new) head node and you don't need to consume the stack. Then, at the end, you just reverse the (singly-linked list):

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

If you really, really wanted, you could re-cast this using your ListNode structure if you wanted (but, why?).

Having said that, if you want to build the list in-order, without reversing anything, just use a 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 ] ) ))

You can also make a lazy-list. My favorite way is by using 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 ] ) ))

Shlomi · Answer 2 · 2018-08-08T23:06:03.637

You seem to be missing the key feature of defining a list as the algebraic datatype list x = (x, list x) | nil

The point of this definition is its recursiveness, right? so using this definition, if you want to add an item x to an existing list of xs, you simply do new-list = (x, list x).

In code, your add-node function should be defined as:

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

Now, if you want to add a gazillion items to this list, you wont have a stack-overflow, but because of the recursive definition, your list will be a LIFO style list. The last item you inserted will be the first item you see. It is O(1) to get the head and O(n) to get anything else. That is implied by the definition. In your current definition of add-node, every insertion is of O(n), which might imply that you are using the wrong data structure.

It is a very common idiom in functional programming such as lisps (cons lists) and haskell. A reverse operation is quite trivial to write should you want to turn the list around. However, if that is the case, you might want to use a different data structure all-together, such as clojure's vectors or difference lists (see this wonderful answer by Bill Burdick)

score 1 · Answer 3 · answered Aug 02 '18 at 21:03

the strategy is to collect list nodes in the reverse order, and then to rebuild the list bottom up. Could be something like this:

(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}}}

the recur part "reverses" the list, while reduce "appends" accumulated value (starting from new node) to the following one, leading to the same structure.

now your function would not lead to stackoverflow (well trying to print the result would still lead to it, but for another reason: the map is just to deep to be printed)

But right, this is only good for education )

Possible to rewrite this to avoid stackoverflow?

3 Answers3