Confluently Persistent Catenable Deques

Summary

CPCD is an ML structure implementing a fully persistent double-ended queue supporting addition, removal, and inspection at both ends as well as concatenation of two lists in amortized constant time, as described in this paper:

Kaplan, Haim, and Chris Okasaki, and Robert E. Tarjan. Simple Confluently Persistent Catenable Lists (1998). Draft.
Currently available at: http://www.research.att.com/~hkl/papers/implicitJ.ps

The key five operations from the paper, push, pop, inject, eject, and catenate (as @) are supported (makelist is not needed, since push(x, EmptyDeque) is equivalent). In addition, most operations in the basis library's LIST and LISTPAIR signatures have analogous versions for CPCDs available. For details, see the signature description.

If you have a part of an application which uses standard ML lists and applies @ and last to long lists, you may benefit from substituting CPCDs for them. To do this, follow these steps:

Open the OpenCPCD structure, which will replace top-level list functions and constructors with their CPCD equivalents.
Replace references to nil or [] with EmptyDeque.
It is not possible to pattern match head/tail combinations on CPCDs. Replace pattern matching on lists with let statements involving hd and tl or CPCD.pop.
Wrap any list literals [x,y,...,z] with CPCD.fromList.

Here's a sample, using normal lists:

(* Gives a list reversed with each element doubled *)
fun doubleRev(nil) = nil
  | doubleRev(first::more) =
    doubleRev(more) @ [first, first]

and using CPCDs:

open OpenCPCD
(* Gives a deque reversed with each element doubled *)
fun doubleRev(EmptyDeque) = EmptyDeque
  | doubleRev(q) =
    let val (first, more) = CPCD.pop(q) in
        doubleRev(more) @ CPCD.fromList[first, first]
    end

or:

open OpenCPCD
fun doubleRev(EmptyDeque) = EmptyDeque
  | doubleRev(q) =
    let val first = hd q
        val more  = tl q  in
        doubleRev(more) @ (first::first::EmptyDeque)
    end

Signature Description

The `CPCD` structure

Summary

datatype 'a deque = EmptyDeque | ...
val push     : 'a * ('a deque) -> 'a deque
val ::       : 'a * ('a deque) -> 'a deque
val inject   : 'a * ('a deque) -> 'a deque
val @@       : ('a deque) * 'a -> 'a deque
val tl       : 'a deque -> 'a deque
val pop      : 'a deque -> 'a * ('a deque)
val dropLast : 'a deque -> 'a deque
val eject    : 'a deque -> 'a * ('a deque)
val @        : ('a deque) * ('a deque) -> 'a deque
val take     : ('a deque) * int -> 'a deque
val drop     : ('a deque) * int -> 'a deque
val takeEnd  : ('a deque) * int -> 'a deque
val dropEnd  : ('a deque) * int -> 'a deque
val rev      : 'a deque -> 'a deque

val hd       : 'a deque -> 'a
val last     : 'a deque -> 'a
val nth      : ('a deque) * int -> 'a

val null     : 'a deque -> bool
val length   : 'a deque -> int

val fromList : 'a list -> 'a deque
val toList   : 'a deque -> 'a list

val app      : ('a -> unit) -> 'a deque -> unit
val appRev   : ('a -> unit) -> 'a deque -> unit
val foldl    : ('a * 'b -> 'b) -> 'b -> 'a deque -> 'b
val foldr    : ('a * 'b -> 'b) -> 'b -> 'a deque -> 'b
val map      : ('a -> 'b) -> 'a deque -> 'b deque
val find     : ('a -> bool) -> 'a deque -> 'a option
val findLast : ('a -> bool) -> 'a deque -> 'a option
val filter   : ('a -> bool) -> 'a deque -> 'a deque
val exists   : ('a -> bool) -> 'a deque -> bool
val all      : ('a -> bool) -> 'a deque -> bool

Producing new queues

These are the simpler operations; see Iteration operations for some more ways of producing new queues.

EmptyDeque

A constructor for an empty deque. Use to represent an empty CPCD or to pattern-match an empty CPCD, as in:

let fun len(EmptyDeque) = 0
      | len q           = 1 + len(tl q)
in
    len(1::2::EmptyDeque)
end

push e q

Adds e to the front of q, giving the resulting deque (amortized O(1))

e::q

Convenient alias for push (ex. elem1::elem2::elem3::EmptyDeque)

inject e q

Adds e to the end of q, giving the resulting deque (amortized O(1))

q @@ e

Convenient alias for inject (ex. EmptyDeque @@ elem1 @@ elem2 @@ elem3)

tl q

Gives q with its first element removed (amortized O(1))

pop q

Returns a pair (x,q₂), where x is the element at the front of q, and q₂ is q with x removed from the front (amortized O(1)). Equivalent to (hd q, tl q).

dropLast q

Gives q with its last element removed (amortized O(1))

eject q

Returns a pair (x,q₂), where x is the element at the end of q, and q₂ is q with x removed from the end (amortized O(1)). Equivalent to (last q, dropLast q).

q1 @ q2

Concatenates two deques into one resulting deque (amortized O(1))

take q n

Gets first n elements of q as a deque (O(n), n=argument)

drop q n

Gets q with first n elements removed (O(n), n=argument)

takeEnd q n

Gets last n elements of q as a deque (O(n), n=argument)

dropEnd q n

Gets q with last n elements removed (O(n), n=argument)

rev q

Returns a deque with the same elements as q in the opposite order (O(n), n=length q)

Extracting elements

hd q

Gets element at front of q (O(1)). If also removing, consider using pop.

last q

Gets element at end of a deque (O(1)). If also removing, consider using eject.

nth q n

Gets nth element (zero-based) from the beginning of q (O(n), n=argument)

Tests

null q

Determines if q is empty (O(1))

length q

Determines number of elements in q (O(n), n = length q)

Conversion operations

fromList lst

Makes a deque containing this list's contents in order (O(n), n=list size)

toList q

Makes a list containing q's contents in order (O(n), n=length q). Useful for viewing the contents of a CPCD at the top-level.

Iteration operations

These are all from signature LIST, except they operate on CPCDs instead.

app f q

Applies f to each element of q in order (O(n), n=length q)

appRev f q

Applies f to each element of q in reverse order (O(n), n=length q)

foldl f init q

Equivalent to List.foldl f init (CPCD.toList q), but with no space use (time O(n), n=deque size)

foldr f init q

Equivalent to List.foldr f init (CPCD.toList q), but with no space use (time O(n), n=deque size)

map f q

Equivalent to List.map f init (CPCD.toList q), but with no space use (time O(n), n=deque size)

find f q

Applies f to the elements of q in order, returning SOME x for the first one it returns true for, or NONE if it never does (worst-case time O(n), n=length q)

findLast f q

Applies f to the elements of q in reverse order, returning SOME x for the first one it returns true for, or NONE if it never does (worst-case time O(n), n=length q)

filter f q

Returns a queue containing the elements of q for which f returns true, preserving relative order (time O(n), n=length q)

exists f q

Returns true only if f(e)=true for some element e of q (worst-case time O(n), n=length q)

all f q

Returns true only if f(e)=true for every element e of q (worst-case time O(n), n=length q)

The `CPCDPair` structure

This structure supports operations analogous to those in the LISTPAIR signature, but operate on CPCDs instead.

Summary

CPCD.deque will be abbreviated deque below, for clarity.

val zip    : 'a deque * 'b deque -> ('a * 'b) deque
val unzip  : ('a * 'b) deque -> 'a deque * 'b deque
val map    : ('a * 'b -> 'c) -> 'a deque * 'b deque -> 'c deque
val app    : ('a * 'b -> 'c) -> 'a deque * 'b deque -> unit
val foldl  : ('a * 'b * 'c -> 'c) -> 'c -> 'a deque * 'b deque -> 'c
val foldr  : ('a * 'b * 'c -> 'c) -> 'c -> 'a deque * 'b deque -> 'c
val exists : ('a * 'b -> bool) -> 'a deque * 'b deque -> bool
val all    : ('a * 'b -> bool) -> 'a deque * 'b deque -> bool

zip(q1,q2)

Gets a deque of pairs (i,j) such that the nth pair has i=nth(q1,n) and j=nth(q2,n). If q1 and q2 are of unequal length, the tail of the longer one is ignored. (Time: O(min(m,n)), where m=length q1, n=length q2)

unzip q

Given a deque q of pairs, extracts two deques, one from the first elements of the pairs, and from the second elements (Time: O(n), n=length q)

map f (q1, q2)

Maps a function over two deques in parallel. Equivalent to CPCD.map f (zip (q1, q2)), without the extra space usage. (Time: O(min(m,n)), m=length q1, n=length q2)

app f (q1, q2)

Applies a function over two deques in parallel. Equivalent to CPCD.app f (zip (q1, q2)), without the extra space usage. (Time: O(min(m,n)), m=length q1, n=length q2)

foldl f init (q1, q2)

Folds f over two deques, passing f (x,y,soFar), where x is from q1, y from q2, and soFar is the result that has been built up so far. (Time: O(min(m,n)), m=length q1, n=length q2)

foldr f init (q1, q2)

Folds f over two deques, passing f (x,y,soFar), where x is from q1, y from q2, and soFar is the result that has been built up so far. (Time: O(min(m,n)), m=length q1, n=length q2)

exists f (q1, q2)

Returns true iff f(x,y) returns true for some corresponding pair of elements from the two queues. (Time: O(min(m,n)), m=length q1, n=length q2)

all f (q1, q2)

Returns true iff f(x,y) returns true for every corresponding pair of elements from the two queues. (Time: O(min(m,n)), m=length q1, n=length q2)

Download

The implementation, including signatures and code, is contained in cpcd.sml and cpcdpair.sml. The archive cpcd.tar.gz contains both of these.

cpcd.tar.gz
cpcd.sml
cpcdpair.sml

If you encounter any problems or need help using CPCDs, please contact me for assistance.

To-Do

In the future, I need to do some of these:

Replace buffers, currently implemented with standard lists, with a specially-designed data type based on arrays and vectors, in order to make the representation more compact and avoid time allocating conses.
Implement a split operation more efficient than using two of take/drop/takeEnd/dropEnd.
Get SML/NJ's pretty-printer to display deque values as compactly as lists.
Your suggestions

Back to code

Back to main page

The author, Derrick Coetzee, waives all rights to all content under the Creative Commons Zero Waiver (CC0 1.0 Universal).

Confluently Persistent Catenable Deques

Summary

Signature Description

The CPCD structure

Summary

Producing new queues

Extracting elements

Tests

Conversion operations

Iteration operations

The CPCDPair structure

Summary

Download

To-Do

The `CPCD` structure

The `CPCDPair` structure