[erlang-questions] how are implemented lists?

Matthias Lang <>
Mon May 18 22:28:31 CEST 2015


Hi,

I've read the answers to your question that have come in so far, and
I'm left wondering if the answer you're looking for is: "a list in
Erlang is a singly-linked list". But maybe that's obvious.

If you haven't already come across it, an interesting book about the
sorts of data structures you can implement in languages like Erlang is

   "Purely Functional Data structures" by Chris Okasaki

a subset of the ideas in that book are in a paper by the same author:

   http://www-2.cs.cmu.edu/~rwh/theses/okasaki.pdf

Keep in mind that some/many of Okasaki's structures require a lazy
language, which Erlang isn't.

I think a skip list is something you can only (directly) implement in
a language which allows destructive updates, i.e. not as an Erlang
program.

A _quick_ glance at what's happened with skip lists since the early
90s suggests that you can implement them as trees, which in turn
_might_ mean it's possible directly in Erlang, contrary to what I claim
in the previous paragraph. E.g.:

  http://www.cs.clemson.edu/~bcdean/paper11.html

Maybe someone up to speed on this can comment; I'm a bit curious, but
not curious enough to do more than leaf through that paper.

Matthias

----------------------------------------------------------------------
Date: 18. May 2015
From: Benoit Chesneau <>
To 
Subject: [erlang-questions] how are implemented lists?


> 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?
>
> - benoît

> _______________________________________________
> erlang-questions mailing list
> 
> http://erlang.org/mailman/listinfo/erlang-questions


More information about the erlang-questions mailing list