Queues and Deques in SML

Companion source code to

Chris Okasaki
Simple and Efficient Purely Functional Queues and Deques
Journal of Functional Programming, 5(4):583-592, October 1995.
(Copyright by Cambridge University Press)

All companion source code is written for SML/NJ (version 0.93).

We give implementations of three different data structures.

stream.sig, stream.sml: slightly customized implementation of lazy lists used in implementing queues and deques
queue.sig, queue.sml: queues with O(1) worst-case performance
deque.sig, deque.sml: double-ended queues with O(1) worst-case performance

For comparison, three further implementations of queues are provided.

queue.std.sml: the standard paired list implementation. O(n) worst-case performance, but O(1) amortized performance provided you use the queues in a "single-threaded" manner.
queue.lazy.sml: an intermediate design described in the paper. O(log n) worst-case performance, but O(1) amortized performance without the above restriction.
queue.hm.sml: the classic implementation of O(1) queues, described in Hood and Melville, "Real-time queue operations in pure Lisp", IPL 13(2). As you can see, it is quite a bit more complicated than the implementation in queue.sml.

A fair comparison for our implementation of deques can be found in Chuang and Goldberg, "Real-time deques, multihead Turing machines and purely functional programming", FPCA '93. They present an extension to the Hood/Melville approach to handle double-ended queues. They also provide SML source code.