What are improper lists for?

Question

This is a follow-up of my previous question: Why do we need nil? Clearly, proper lists are used most of the time. But what is the purpose of an improper list?

Answer 1

For no good reason. The only thing that improper lists are truly good for is as part of the syntax for association lists—and even there, a custom syntax for key-value pairs would be better. Any use you can think of for improper lists can be better implemented with record types—which, after all, subsume lists: you can define Lisp lists in terms of records, but not the other way around (because lists don't allow you define data structures whose type is disjoint from all other types in the language).

The abuse of pairs and lists to represent all types of data is what I like to call Lisp programmer's disease, and it's a real shame that so many Lisp advocates advocate for it. I've had to clean up that stuff way too many times.

Answer 2

Great Question! (Well, I like Chris' rewrite of it, anyway...). In my experience, the most common use of improper lists is as lightweight two-element structures.

The reasoning goes like this: "gee, I need a two-element structure. Ooh, wait, why not just use 'cons'? It's built-in, and it's really well-supported by the built-in quoting syntax. What the heck, I'll do it."

In particular, built-in operations such as "assoc" are often implemented in a way that assumes that it's given a list of improper two-element lists.

Answer 3

The existence of the improper list is a natural consequence of the existence of the fundamental building blocks cons, car, and cdr. It's at the heart of lisp that these three form the basis for all sorts of more complex data types. Somehow singling out the improper list for banishment would require imposing arbitrary restrictions.

Answer 4

An "improper list" is a vague term for any data type other than a list that is build using cons.

One example, as John says, is to use cons pairs in the same way one might use tuples in ML.

Another example is as a variation on lists. For example, one might define a stream as follows:

;; A Stream-of-X is one of
;;   - null, ie '()
;;   - (cons X Stream-of-X)
;;   - a procedure taking no arguments and returning a Stream-of-X result

;; nats-from : nat -> Stream-of-nat
(define (nats-from n)
  (cons n (lambda () (nats-from (+ n 1)))))