[erlang-questions] documentation of data structures

David Hopwood david.hopwood@REDACTED
Thu Dec 13 06:15:05 CET 2007

Matej Kosik wrote:
> Andras Georgy Bekes wrote:
>> -queue: The doc doesn't say anything about the implementation, 
>> only: "implements FIFO queues in an efficient manner".
>> It states that "all operations has an amortised O(1) running time", 
>> except for some, that are "probably O(n)". This is rather vague.
> Check the implementation. You will reveal that the operations for adding/removing elements from/to
> the head/tail can have O(1) complexity in some cases but in some cases they will have O(n) complexity.
> It would be particularly attractive, if someone implemented `queue' (with the same signature and
> semantics of operations) where those operations would have always O(1) complexity.

Persistent FIFO queues with O(1) worst-case complexity of add, remove,
and even catenation (surprisingly) are possible. See

  Chris Okasaki,
  Simple and Efficient Purely Functional Queues and Deques,
  Journal of Functional Programming 5(4) pages 583-592, October 1995.


  Haim Kaplan, Robert E. Tarjan,
  Purely Functional, Real-Time Deques with Catenation,
  Journal of the ACM, 46(5) pages 577-603, 1999.

David Hopwood

More information about the erlang-questions mailing list