Simple confluently persistent catenable lists

We consider the problem of maintaining persistent lists subject to concaten ation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive each operation produces a new list incor porating the change, while keeping intact the list or lists to which it app lies. Although general techniques exist for making data structures persiste nt, these techniques fail for structures that are subject to operations, su ch as catenation, that combine two or more versions. In this paper we devel op a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. O ur implementation is functional if we allow memoization.