Purely(ish) functional data structure with fast append and forward iteration

Question

I find I have need for a data structure with a specific set of requirements:

• It represents an immutable sequence of values (fixed sized integers if this matters)
• Appending a new value to the end (and returning a new sequence) needs to be extremely fast and memory efficient. Ideally amortised O(1) and sharing the entire prefix, but there's no specific hard complexity requirement and O(log(n)) would probably be OK too.
• Getting the length of a sequence needs to be cheap (obviously I can add this in after the fact with a wrapper if necessary)
• I need to be able to efficiently iterate the sequence in the forward direction
• I need to be able to lexicographically compare two sequences of the same length in the forward direction efficiently (this follows from the previous property, but might have simpler implementations and has fairly specific iteration patterns)
• Sharing of prefixes is very common in the expected workloads, so solutions like vlists or copy-on-append aren't practical because the workload will essentially always trigger a full copy.
• (practical rather than theoretical constraint but...) The simpler the design the better, because I'm almost certainly going to have to implement this from scratch in a couple of different languages, including C (with reference counting)

Non-constraints:

• Although the data structure itself has to represent immutable sequences, I don't mind a certain amount of mutation of the values if it's invisible (it would be nice to avoid)
• I certainly don't mind depending on e.g. some source of randomness
• It's OK if the forward iteration depends on some sort of external data structure with extra space requirements

Obviously the ideal would be to just have a length prefixed cons list, but the forward iteration requirement makes that sub-optimal.

The following are the two things I've considered so far:

• Just use a cons-list anyway and reverse it in an external buffer prior to iteration. Downsides: Forward iteration becomes fairly expensive, particularly for cases where I'm likely to stop the iteration after only one or two elements (which is a common case because of lexicographic comparison being a major use case here).
• A tree of bounded balance - it stores the size efficiently, has relatively cheap append and iteration. Downsides: Kinda fiddly to implement correctly, unclear whether the relatively high constant factors and the logarithmic complexity make it a win in practice.
• A skip list. Downsides: Same as the upsides really - it's about halfway between the previous two in terms of complexity and performance. Requires more book-keeping for iteration than the others, but it's probably tolerable.

So of the three the skip list looks like it might be the best option and "just use a cons list and optimise later" looks like the one I'm most likely to start with, but I'm not exactly well versed in the purely functional data structure literature, so I was hoping there were a better option I was overlooking. Any suggestions?

Answer 1

You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions. To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally. Instead of doing the reverse&append all at once, taking O(N) time, you need to be able to do just a few steps of the reverse&append every time you add a new element or remove/traverse through an element.

Hood and Melville showed one way to do this back in 1980. For your purposes, their approach would be straightforward to adapt to C (with reference counting).

In the early to mid 90's, I showed several ways to do this, some in O(1) worst-case time and some in O(1) amortized time. Most of these ways depended on lazy evaluation, which initially might seem hard to do in C, but in fact, there are only a very small of "shapes" needed for the lazy evaluation, each of which would be easy to represent using an ordinary node in C.

For example, a "Rotate" node has pointers to three sublists: L, R, and A. Doing one step of the rotation replaces the "Rotate" node with an ordinary list node containing the head of L, and a pointer to a new Rotate node containing the tail of L, the tail of R, and the result of adding the head of R to the front of A. Making this translation into explicit Rotate nodes instead of using generic lazy evaluation also means that you get O(1) worst-case bounds instead of O(1) amortized bounds.

Answer 2

Sounds like you are asking for a functional queue. The standard implementation of that is:

data Queue a = Queue [a] [a]

empty = Queue [] []
enqueue x (Queue xs ys) = Queue xs (x:ys)
dequeue (Queue [] ys) = dequeue (Queue (rev ys) [])
dequeue (Queue (x:xs) ys) = (x, Queue xs ys)

This has constant time enqueue and amortised constant time dequeue. See also Chris Okasaki's classic paper for more details.

Answer 3

Sorry, on writing this up and thinking about it a bit further I've come up with what is probably a good answer. Rubber ducks for the win. There turns out to be something that combines a lot of the good properties of the three ideas I already had, but is made vastly easier by the fact that we only need to append.

The basic data structure is pretty close to that of a tree of bounded balance:

data Tree a = Bin Int (Tree a) (Tree a) | Leaf a | Nil

But we maintain the invariant that it always represents a complete left-leaning binary tree.

Append is then implemented as follows:

append Nil t = Leaf t
append (Leaf s) t = Bin 2 (Leaf s) (Leaf t)
append (Bin n u v)@l t | size u == size v = Bin (n + 1) l (Leaf t)
append (Bin n u v) t = Bin (n + 1) u (append v t)

Where size is just the obvious:

size Nil = 0
size (Leaf _) = 1
size (Bin n _ _) = n

Appending is fairly cheap because the left-leaning property means that right subtrees are as small as possible. Iteration is relatively cheap because of the strong log(n) bound.

I feel like there's a variant solution to this where we always keep the first element of the sequence on the Bin node instead of deep in the left-most leaf, but I haven't quite figured out the balancing act for that. Edit: actually it's easy. You just have to treat the key as part of the left tree and everything carries over - the invariant is now size left + 1 >= size right. It makes the join operation a bit more expensive when you have to rebalance but it's still only log n.

The following is a minimal implementation of this modified form (it also ditches the size annotation because you don't need it on every node because the tree is left-leaning):

import Data.Bits ((.&.), (.|.), shiftR, clearBit, xor)

data AppendNode a = Bin a (AppendNode a) (AppendNode a) | Nil

data AppendTree a = AppendTree Int (AppendNode a)

size :: AppendTree a -> Int
size (AppendTree n _) = n

tip a = Bin a Nil Nil

empty = AppendTree 0 Nil

append :: AppendTree a -> a -> AppendTree a
append (AppendTree n x) a = AppendTree (n + 1) (appendWithSize n x a)

appendWithSize :: Int -> AppendNode a -> a -> AppendNode a
appendWithSize 0 Nil a = tip a
appendWithSize n Nil _ = error "Non-zero size in Nil node"
appendWithSize n (Bin s x y) a | isPowerTwo n = Bin s (join x y) (tip a)
appendWithSize n (Bin s x y) a = Bin s x (appendWithSize (clearTopBit n) y a)

join :: AppendNode a -> AppendNode a -> AppendNode a
join Nil x = x
join x Nil = x
join (Bin s x y) z = Bin s (join x y) z 

-- Some needed bit twiddling functions

isPowerTwo :: Int -> Bool
isPowerTwo 0 = False
isPowerTwo n = (n .&. (n - 1)) == 0

clearTopBit :: Int -> Int
clearTopBit n = xor n (highestBitMask n)

highestBitMask :: Int -> Int
highestBitMask x1 = let x2 = x1 .|. x1 `shiftR` 1
                        x3 = x2 .|. x2 `shiftR` 2
                        x4 = x3 .|. x3 `shiftR` 4
                        x5 = x4 .|. x4 `shiftR` 8
                        x6 = x5 .|. x5 `shiftR` 16
                        x7 = x6 .|. x6 `shiftR` 32
                     in x7 `xor` (x7 `shiftR` 1)

toList :: AppendTree a -> [a]
toList (AppendTree _ t) = prepend  t []
    where
        prepend Nil ls = ls
        prepend (Bin s x y) ls = s : (prepend x . prepend y $ ls)

fromList :: [a] -> AppendTree a
fromList ls = work 0 Nil (reverse ls)
    where work n x [] = AppendTree n x
          work n x (t:ts) = append (work n x ts) t

I'm not going to accept this answer for now in the hope that there's a still better one (in particular I'd like cheaper appends), but this seems like a pretty good compromise data structure.

Answer 4

I haven't done a thorough analysis but I think you get amortized O(1) append and O(m) traversal for the first m elements by just keeping two lists where the first has the front of the sequence in order and the second has the back in reverse order.

Append conses onto the second list in the common case but if the front and back are the same length concatenates the front and the reversed back as the new front with the new element a singleton back list.

Iteration can go through the front of the sequence trivially and delay reversing the last part until it's already gone through at least half the sequence and built up enough credits to pay for the reversal.

Here's some Haskell code

data AppendList a = AppendList Int Int [a] [a]
  deriving Show

empty = AppendList 0 0 [] []

append :: AppendList a -> a -> AppendList a
append (AppendList 0 0 [] []) x = AppendList 1 0 [x] []
append (AppendList n m h t) x | n == m = AppendList (n+m) 1 (h++reverse t) [x]
                              | otherwise = AppendList n (m+1) h (x:t)

size (AppendList n m _ _) = n+m

toList :: AppendList a -> [a]
toList (AppendList _ _ h t) = h ++ (reverse t)

fromList :: [a] -> AppendList a
fromList xs = AppendList (length xs) 0 xs []

This is different from Andreas's answer in that it is better matched to the pattern of operations laid out by David. The amortization analysis yielding O(1) amortized dequeue is not valid when versions other than the most recent are accessed, see Okasaki's Simple and Efficient Purely Functional Queues and Deques for some discussion of this. The reversal contained in dequeue is considered paid for by the insertion of the items but if the same queue is iterated many times then only the reversal for the first iteration has been paid for and the remaining are an extra cost. Even simple memoization of dequeue results is not enough to address as shown by this example:

x = append (append (append empty 1) 2) 3   -- credit of 3 units
a, y = dequeue x                           -- charge 3 units, 0 balance
a', y' = dequeue x                         -- 0 cost due to memoization, 0 balance
z = append x 4                             -- credit of 1 unit
b, z = dequeue z                           -- cost of 4, -3 balance

Okasaki shows how to do get O(1) worst-case for enqueue and dequeue by splitting work between enqueue and dequeue and careful management of laziness, but this implementation would be quite challenging to do in C.

On the other hand, my approach achieves O(m) amortized time for iterating the first m elements of the sequence. Like Okasaki, I split work between append and iteration but in away that seems straightforward to implement in a language like C.

This seems well matched to David's use case in that iteration of (at least) the first half of the sequence is as efficient as a simple linked list so that ordering comparisons that only need to access the first half of the sequences are quite fast.

However, in the more careful analysis I'm doing now, I see that my implementation suffers from the a similar problem as the simple functional queues for reuse of several versions, except that mine occurs for append operations as seen below.

x = AppendList 4 4 [1,2,3,4] [8,7,6,5]  -- building the back list gives a credit of 4
y = append x 10                         -- does a reverse of cost 4, 0 balance
z = append x 11                         -- does a reverse of cost 4, -4 balance

Performing the rebalance with probability 1/(size of front list) would at least spread the pain around but doesn't make it go away. I don't see an easy way to deal with this issue, but maybe given the usage patterns it's not that big a deal?