I know this question is old, but no one said anything about difference
lists and since you say you really just want something you can append
and prepend with, it sounds like difference lists might help you.
They don't seem popular in Clojure, but they are VERY easy
to implement and a lot less complex than finger trees, so I made a
tiny difference list library, just now (and even tested it). These
concatenate in O(1) time (prepend or append). Converting a difference
list back to a list should cost you O(n), which is a nice trade-off if
you're doing a lot of concatenation. If you're not doing a lot of
concatenation, then just stick to lists, right? :)
Here are the functions in this tiny library:
dl: A difference list is actually a function which concats its own
contents with the argument and returns the resulting list. Every time
you produce a difference list, you're creating a little function that
acts like a data structure.
dlempty: Since a difference list just concats its contents to the
argument, an empty difference list is the same thing as the identity
function.
undl: Because of what difference lists do, you can convert a
difference list to a normal list just by calling it with nil, so this
function isn't really needed; it's just for convenience.
dlcons: conses an item to the front of the list -- not totally
necessary, but consing is a common enough operation and it's just a
one-liner (like all of the functions, here).
dlappend: concats two difference lists. I think its definition is
the most fun -- check it out! :)
And now, here's that tiny library -- 5 one-line functions that give you a O(1)
append/prepend data structure. Not bad, eh? Ah, the beauty of Lambda
Calculus...
(defn dl
"Return a difference list for a list"
[l]
(fn [x] (concat l x)))
; 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 thing:
((dl '(1 2 3)) '(4 5 6))
Have fun with difference lists!
Update
Here are some definitions that may be more difficult to understand but I think are 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 lets you say something like this:
(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))
Which would return
(1 2 3 4)
