How do I append one element to a list as efficiently as possible-CodePudding

At the end of CLOJURE for the BRAVE and TRUE's Chapter 4 there's an exercise: make an append function that appends a new entry to a list.

What's the most efficient way to do so?

From what I understand of datatypes in general, if conj prepends elements to a list, that simply means that consistently appending to a list is either silly or the choice of using a list type was silly.

Anyway, the solution I've written is this

(defn append
  [lst item]
  (into '() (conj (into '() lst) item)))

Well, that's actually the same as

(defn append
  [lst item]
  (reverse (conj (reverse lst) item)))

I believe, so probably is costly because I reverse the list twice?

Another solution I could think of is

(defn append
  [lst item]
  (apply list (conj (apply vector lst) item)))

But they all seem to traverse the sequence of values twice, so I don't see why any one shoiuld be better than another.

Is there the proper way to accomplish the task?

CodePudding user response：

There is a reason, why conj adds a new item at the start of the list and not at its end. Because you have to traverse the list to add something at its end. This is not very efficient. And it is because of the nature of a linked list. That's why in lisp you cons new items onto a list and at the very end reverse it. This way, you traverse the list just once while building it.

In Clojure, if you want to add to a list at the end, it is more idiomatic not to use a list but instead the vector type. On a vector, conj adds right to the end.

But let's say, you want to traverse a list once and add to the end.

That is actually:

(defn my-append [lst item] (concat lst (list item)))

(my-append '(1 2 3) 4)
;; (1 2 3 4)

but as I said, if you want to add repeatedly at the end, don't use a list, but a vector and conj to the end.

;; more idiomatic clojure in thisst to add something at its end. This is not very efficient. And it is because of the nature of a linked list. Tha case

(def l [1 2 3])

(conj l 4) ;; [1 2 3 4] ;; unbeatable in efficience, because no traversal!

;; and convert to a list
;; e.g.
(def v (conj l 4))
(seq v)    ;; (1 2 3 4)

CodePudding user response：

to avoid the double traversal, you could use the classic recursive approach. Something like this:

(defn append [lst item]
  (loop [res [] lst lst]
    (if (seq lst)
      (recur (conj res (first lst))
             (rest lst))
      (seq (conj res item)))))

so, it just rebuilds the list from scratch. To make it's performance better in clojure, you can optimize it with transient collection:

(defn append' [lst item]
  (loop [res (transient []) lst lst]
    (if (seq lst)
      (recur (conj! res (first lst))
             (rest lst))
      (seq (persistent! (conj! res item))))))

but yes, as another answer proposes, you should carefully pick the proper data structure for every specific task, so in practice you would want to use vector.

As of concat variant, it comes for free (since it is lazy), but it has this known pitfall, which is stack overflow on applying a lot of stacked lazy functions:

user> (defn append-concat [lst item]
        (concat lst [item]))

user> (reduce append-concat () (range 1000000))
;; Error printing return value (StackOverflowError) at clojure.lang.LazySeq/sval (LazySeq.java:42).