[erlang-questions] Irregular list
Ladvánszky Károly
Just getting acquainted with this wonderful system, I’ve run into the following issue:
The shell seems to accept a structure like this: [a | b].
is_list([a | b]) returns true but length([a | b]) raises an exception.
Is it like an “open list” found in some programming languages?
Any help would be appreciated,
LKaroly
Jachym Holecek
> Just getting acquainted with this wonderful system, I’ve run into the
> following issue:
>
> The shell seems to accept a structure like this: [a | b].
>
> is_list([a | b]) returns true but length([a | b]) raises an exception.
>
> Is it like an “open list” found in some programming languages?
What might be confusing here is that 'is_list()' is actually a slight
misnomer, [_ | _] is really just a pair (aka "cons cell") regardless
of what values are held as head + tail. The length() function expects
a "proper list", which is [] or a pair such that its second component
is a proper list.
I'm not familiar with the term "open list", but hope the above helps.
-- Jachym
Joe Armstrong
lisp, or think
"liknked list" in C) - internally it's a pair
of tagged values - the first value in the pair is the head of the
list. The second value
is the tail of the list, an so should point to a list or nil. If the
tail points to
nil or a list then it is a proper list, otherwise it's an improper list.
Most library functions will behave strangely when presented with improper
lists - so don't use them!
/Joe Armstrong
2009/2/12 Ladvánszky Károly <l...@digicart.hu>:
> _______________________________________________
> erlang-questions mailing list
> erlang-q...@erlang.org
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
Mikael Pettersson
> Just getting acquainted with this wonderful system, I’ve run into the
> following issue:
>
>
>
> The shell seems to accept a structure like this: [a | b].
>
>
>
> is_list([a | b]) returns true but length([a | b]) raises an exception.
is_list/1 only inspects the top-most node of the structure and tests
if it's a "list cell" or not. It's poorly named and corresponds to
testing for a "cons" in Lisp dialects.
> Is it like an “open list” found in some programming languages?
Wouldn't know. Never heard of that one.
Zvi
technicaly [a|b] is not a proper list, it's what called in LISP a "cons-cell"
(a . b) in proper list cdr (i.e. tail) field of last element must be nil (or
[] ) in Erlang.
> _______________________________________________
> erlang-questions mailing list
> erlang-q...@erlang.org
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
--
View this message in context: http://www.nabble.com/Irregular-list-tp21977982p21979837.html
Sent from the Erlang Questions mailing list archive at Nabble.com.
Zvi
too bad there is no single pattern to test for list, instead of [] and [_|_]
.
To test for proper list:
is_proper_list([_|T]) -> is_proper_list(T);
is_proper_list([]) -> true;
is_proper_list(_) -> false.
or from shell:
5> F = fun([_|T],F) -> F(T,F); ([],_) -> true; (_,_) -> false end.
#Fun<erl_eval.12.113037538>
6>
7> F([a|b],F).
false
8> F([a,b],F).
true
9> F([],F).
true
10> F([a,b|c],F).
false
11> F([a,b|[]],F).
true
Zvi
--
View this message in context: http://www.nabble.com/Irregular-list-tp21977982p21980109.html
Ladvánszky Károly
Thanks everybody for the help.
Sorry for the confusing term ‘open list’; I wished to refer to Lisp’s/Scheme’s unterminated lists.
LKaroly
Mihai Balea
the concept of cons cells? Wouldn't a tuple be more generic?
Is there any practical use of "improper lists" in Erlang?
Mihai
Paul Fisher
> 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...
--
paul
Jachym Holecek
> Is there any practical use of "improper lists" in Erlang?
A 2-tuple is larger than a cons-cell by one word (or 50% if you
prefer :-), so choosing cons over 2-tuple makes practical sense
if you're about to work with a huge amount of pairs. The dict
module from stdlib seems to be an example.
Note this argument isn't inherent to the problem: With some amount
of work, you could probably tweak erts to represent 2-tuples without
the extra overhead.
Other than size, someone has recently proposed a new function for
a stdlib module (sorry, I forgot the details) that used improper
lists, and after reading the explanation, it felt very intuitive
(more so than the 2-tuple based analogy). So forbidding improper
lists altogether might perhaps be something to regret later on.
Just my two cents, anyway.
-- Jachym
Robert Virding
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?
Tuples and lists have different properties and different uses. Tuples have fixed a size and are typically used when you know how many elements there are. Changing the size of a tuple is basically impossible so if you want to add/remove an another element to a tuple you have to create a new tuple which is different from the old tuple. A typical use for a tuple is when you want to return more than one value from a function where you return a tuple containg the values.
Lists, on the other hand, are dynamic objects. It is easy and cheap to add/remove elements to/from the front of the list, the without having to copy the rest of the list. It is also very easy to step over the elements of a list. A list is built up of pairs, cons cells, where the first element, the head, of the pair is the element of the list while second element, the tail, points to the next pair/cons cell of the list. A pair is written in Erlang as [a|b] and a list as [a,b,c,d] which is syntactic sugar for the actual representation which is written as [a|[b|[c|[d|[]]]]]. Note that the tail of the last pair is []. This makes it a what is called a proper list. If the tail of the last pair is not a [] then it is not a proper list. [] is therefore considered to be the empty list as it contains no elements.
Many (most) list processing functions assume that the lists they work on are proper lists, typically by stepping down the list as long as they tail is another list pair until they get to a []. Length/1 is like this. The test is_list/1 is very simple and test whether its arguments is a pair or the empty list []. It does not check the whole list.
Re: Paul Fisher and the dict module. Dict uses lists for example to keep all the values which have the same key. There is one place in dict where a cons-cell is used in what would normally be a 2-element tuple, it does [Key|Listof Values] instead of {Key,ListofValues}, but that is just joke and serves no practical purpose.
I hope this clears up some issues and doesn't add to the confusion,
Robert
Thomas Lindgren
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