[erlang-questions] Irregular list

[Thomas Lindgren]

--- On Thu, 2/12/09, Paul Fisher <pfisher@REDACTED> wrote:
> Mihai Balea wrote:
> > Maybe I'm missing something, but what is the point
> of even allowing  
> > the concept of cons cells? Wouldn't a tuple be
> more generic?
> > Is there any practical use of "improper
> lists" in Erlang?
> 
> FWIW, the dict module uses them...

There are a few of implementation reasons:

First, a cons cell requires 2 words, while a 2-tuple needs 3 words. That's a 50% overhead, not to mention some extra checking.

Second, requiring that lists be proper means you have to check the list cdr every time you cons something. (At least conceptually; a compiler can probably remove some checks where listness can be derived.)

Third, what about using longer tuples to actually save memory? Here, garbage collection becomes an issue. For a list, it's easy to see whether a cons cell is unreachable. For a tuple, it's usually difficult to see that an element is dead and can be collected. Hence you can easily get space leaks. (Though it's not impossible to handle; e.g., lispmachines used cdr-coding, which is the moral equivalent.)

Best,
Thomas