I know this question is old, but no one said anything about the differences of the listings, and since you say you really want something that you can add and add with, it sounds like the differences can help you. They don't seem popular in Clojure, but they are VERY easy to implement and much less complex than finger trees, so I made a tiny library of difference lists just now (and even tested it). These combine in O (1) time (add or add). Converting a list difference back to a list should cost you O (n), which is a good compromise if you do a lot of concatenation. If you don't do a lot of concatenation, then just stick to the lists, right? :)
Here are the features in this tiny library:
dl: A difference list is actually a function that combines its own contents with an argument and returns a resulting list. Each time you create a list of differences, you create a small function that acts like a data structure.
dlempty:. Since the list of differences simply concatenates its contents with an argument, an empty list of differences is the same as the identifier of the function.
undl: Because of the difference lists, you can convert a difference list to a regular list simply by calling it with nil, so this function is not needed; It is just for convenience.
dlcons: moving an element to the top of the list is not completely necessary, but consing is a fairly ordinary operation, and it is just single-line (like all functions, here).
dlappend: Combines two lists of differences. I think his definition is the most interesting - check it out! :)
And so, here is this tiny library - 5 single-line functions that give you O (1) add / add data structure. Not bad, huh? Ah, the beauty of Lambda Calculus ...
(defn dl "Return a difference list for a list" [l] (fn [x] (concat lx))) ; Return an empty difference list (def dlempty identity) (defn undl "Return a list for a difference list (just call the difference list with nil)" [aDl] (aDl nil)) (defn dlcons "Cons an item onto a difference list" [item aDl] (fn [x] (cons item (aDl x)))) (defn dlappend "Append two difference lists" [dl1 dl2] (fn [x] (dl1 (dl2 x))))
You can see it in action with this:
(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))
which returns:
(1 2 3 4 5 6)
This also returns the same:
((dl '(1 2 3)) '(4 5 6))
Enjoy the lists of differences!
Update
Here are some definitions that may be harder to understand, but I think it’s better:
(defn dl [& elements] (fn [x] (concat elements x))) (defn dl-un [l] (l nil)) (defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))
This allows you to say something like this:
(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))
What will return
(1 2 3 4)