[erlang-questions] documentation of data structures

[David Hopwood]

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.
  <http://citeseer.ist.psu.edu/158610.html>

and

  Haim Kaplan, Robert E. Tarjan,
  Purely Functional, Real-Time Deques with Catenation,
  Journal of the ACM, 46(5) pages 577-603, 1999.
  <http://citeseer.ist.psu.edu/570773.html>

-- 
David Hopwood