[erlang-questions] A modest proposal to eliminate tuples

Richard A. O'Keefe ok@REDACTED
Thu Aug 28 01:53:01 CEST 2014

On 28/08/2014, at 6:21 AM, Chris Pacejo wrote:

> Tuples are clearly unnecessary and a wart in Erlang's design.
> Consider all the operations tuples provide:
> Construction: X = {A,B,C}
> Destruction: {A,B,C} = X
> Pattern matching: case X of {foo,B,C} -> ... end
> Note now that these operations are provided equally by lists:
> Construction: X = [A,B,C]
> Destruction: [A,B,C] = X
> Pattern matching: case X of [foo,B,C] -> ... end

They are not, however, provided with equal COST.

Without looking at the implementation, but based on my
knowledge of the WAM, I can tell you that

 - a list of n items could take 2n words
 - a tuple of n items could take n+1 words

 - accessing the kth element of a list takes O(k) time
 - accessing the kth element of a tuple takes O(1) time

 - matching an n-element list pattern against an m-element
   list value fails after O(min(m,n)) time
 - matching an n-element tuple pattern against an m-element
   tuple value fails after O(1) time

 - prepending k elements to an n-element list takes O(k) time
 - prepending k elements to an n-element tuple takes O(k+n) time

The result is that some things will go drastically faster with
lists than with tuples, with other things will go drastically
faster with tuples than with lists.

Scheme has vectors as well as lists, for the same good reasons.
> And note that lists provide the additional functionality of indexing
> and consing, which tuples do not provide.

No, tuples DO provide indexing.  They are very good at it.
> Clearly, using tuples instead of lists provides no benefit,

Halving the amount of memory required is "no benefit"?
O(1) access instead of O(k) is "no benefit"?
> Now, surely detractors will claim that the distinction between tuples
> and lists signals programmer intent, permits bytecode optimization,
> and enables rich typechecking in Dialyzer.

Not me.  What *I* claim is that in *any* programming language
it can be useful to have multiple implementations of the same

Now there is work going back decades on adaptive data structures
which flip "under the hood" from one representation to another
depending on what you are doing with them.  But that puts up the
cost of everything.

>  I claim these purported benefits are bollocks.

Well, they're *your* claims, so if you say so...

>  I, and no doubt others, routinely find the
> need to iterate over tuple elements, and to store unrelated data
> together in a single list.

I've written a lot of code over the years.  I can't remember
when I last had a need to store *unrelated data* together in
a single list, and it's certainly not routine.  Iterating
over tuple elements, YES, but

(1) there is already an EEP proposing tuple generators in
comprehensions, and tuple comprehension.
(2) thanks to the magic of higher-order functions, it is
ALREADY dead simple to iterate over the elements of tuples.
(Just not as pretty as using comprehensions.)

> I hope you all agree, and that we can look forward to a future Erlang
> supporting lists and maps as its sole data constructors.

Such an Erlang would fail to support practically *all* existing
code.  It would be like a revised C++ where vector<T> was there
but T[] was not.  Could be a usable language, but would not
support old code.

More information about the erlang-questions mailing list