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.

Answer 2

I think it's easier to explain this using Scheme.

A list is a chain of pairs that end with an empty list. In other words, a list ends with a pair whose cdr is ()

(a . (b . (c . (d . (e . ())))))   ;; same as  (a b c d e) 

A chain of pairs that doesn't end in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists, as the following equivalent notations show:

 (a b c . d)  (a . (b . (c . d))) 

An example of a usual mistake that leads to the construction of an improper list is:

scheme> (cons 1 (cons 2 3)) (1 2 . 3) 

Notice the dot in (1 2 . 3)---that's like the dot in (2 . 3), saying that the cdr of a pair points to 3, not another pair or '(). That is, it's an improper list, not just a list of pairs. It doesn't fit the recursive definition of a list, because when we get to the second pair, its cdr isn't a list--it's an integer.

Scheme printed out the first part of the list as though it were a normal cdr-linked list, but when it got to the end, it couldn't do that, so it used "dot notation."

You generally shouldn't need to worry about dot notation, because you should use normal lists, not improper list. But if you see an unexpected dot when Scheme prints out a data structure, it's a good guess that you used cons and gave it a non-list as its second argument--something besides another pair or ().

Scheme provides a handy procedure that creates proper lists, called list. list can take any number of arguments, and constructs a proper list with those elements in that order. You don't have to remember to supply the empty list---list automatically terminates the list that way.

Scheme>(list 1 2 3 4) (1 2 3 4) 

Courtesy: An Introduction to Scheme