[erlang-questions] documentation of data structures

Andras Georgy Bekes <>
Fri Dec 7 09:17:13 CET 2007


I've checked the manpage of the new array data structure, and I don't 
find any info about its runtime (and space) compexity. I think not 
knowing the implementation details is OK, but the runtime complexity of 
the most frequently used operations on a data structure is needed in 
the documentation I think.

I've checked (hopefully) every data structure:

- ordsets and orddict: The doc states that they are represented as 
ordered lists. It doesn't mention the complexities of the operations, 
it is OK because the implementation is rather trivial and an Erlang 
programmer is expected to know the runtime behaviour of such 

-sets and dict: The doc states that the representation is not defined.
I think the doc shoud give a worst case complexity of the operations 
that will not change no matter how the implementation changes.

- gb_sets and gb_trees: The doc states the implementation. For gb_trees, 
the complexities are not given. For gb_sets it gives info about the 
complexity on set operations, however, it might be better to give the 
complexities of for each of the operations, instead of just 
separating "set operations" and "lookup (membership testing), insertion 
and deletion".

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

- array: The doc doesn't say anything. Not even that the implementation 
is not defined.

The docs should be made complete and consistent ie. should state the 
same infos in the same style for each of these data structures.


More information about the erlang-questions mailing list