Functional Programming: what is an "improper list"?

Question

Could somebody explain what an "improper list" is?

Note: Thanks to all ! All you guys rock!

Answer 1

I think @Vijay's answer is the best one so far and I just intend to Erlangify it.

Pairs (cons cells) in Erlang are written as [Head|Tail] and nil is written as []. There is no restriction as to what the head and tail are but if you use the tail to chain more cons cells you get a list. If the final tail is [] then you get a proper list. There is special syntactic support for lists in that the proper list

[1|[2|[3|[]]]]

is written as

[1,2,3]

and the improper list

[1|[2|[3|4]]]

is written as

[1,2,3|4]

so you can see the difference. Matching against proper/improper lists is correspondingly easy. So a length function len for proper lists:

len([_|T]) -> 1 + len(T);
len([]) -> 0.

where we explicitly match for the terminating []. If given an improper list this will generate an error. While the function last_tail which returns the last tail of a list can handle improper lists as well:

last_tail([_|T]) -> last_tail(T);
last_tail(Tail) -> Tail.                 %Will match any tail

Note that building a list, or matching against it, as you normally do with [Head|Tail] does not check if the tail is list so there is no problem in handling improper lists. There is seldom a need for improper lists, though you can do cool things with them.