[erlang-questions] : documentation of data structures

[Raimo Niskanen]

I have skimmed both papers...

On Thu, Dec 13, 2007 at 05:15:05AM +0000, David Hopwood wrote:
> 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>
> 

He uses lazy lists with memoization. Not easily adapted to Erlang.



> 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>
> 

This should be implementable, but their best solution seems
reealy complicated. It would require quite some work to
understand all their tricks and structures, and it must
have quite some overhead. But it would be interesting
to give it a shot!



> -- 
> David Hopwood
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB