[erlang-questions] how are implemented lists?

[Richard A. O'Keefe]

On 18/05/2015, at 7:33 pm, Benoit Chesneau <bchesneau@REDACTED> wrote:

> how are implemented lists? What is the algorithm behind them? Especially for key* functions? I am asking myself if i need to implement a skip-list or if the lists module would fit my needs. I indeed need a fast and concurrent data structure that allows me to retrieve the items in order and do pop/tail, while still being abble to remove them by key. Any idea?

It's not clear how a data structure that relies on being
both shared, mutable, and cross-linked, fits into Erlang,
where data structures are (logically) unshared and immutable.

Erlang lists are simple read-only singly-linked lists, and
the key* functions in the lists.erl library file are just
linear searches.

If it weren't for the "concurrent" bit I'd suggest that
one of the set or dictionary data structures in stdlib
might be useful, or one of the Okasaki purely functional
data structures that I thought had been adapted to
Erlang, but can't find.

It looks as though ETS may be the closest thing to what you
need at the moment.

http://stackoverflow.com/questions/3489560/purely-functional-concurrent-skip-list
may be helpful, in a negative sort of way.