7

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?

Community
  • 1
  • 1
day
  • 2,292
  • 1
  • 20
  • 23
  • "What is your _opinion_?" is a dangerous sentence to have in your question. As you know, there is no place for opinions on Stack Overflow, only facts. Seeking opinions will only get your question closed. Already, it has 4 close votes; one further close vote will cause your question to be closed. – C. K. Young Jan 30 '12 at 20:19
  • To save the question, I'll completely rewrite the question. I hope it's okay with you. – C. K. Young Jan 30 '12 at 20:20
  • Thanks for the reminder and editing, Chris. I did not realize that. Well, but it still got closed? – day Jan 31 '12 at 08:23

4 Answers4

8

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.

Luis Casillas
  • 29,802
  • 7
  • 49
  • 102
  • 2
    sacundim, thanks for clearing. I have been puzzled by this lists vs records for quite some time. I would like to read more about it. But googling does not return any useful result. Since you said you had cleaned up that stuff for many times, I'd like to see it more if it exists somewhere. Thanks. – day Jan 31 '12 at 08:33
6

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.

John Clements
  • 16,895
  • 3
  • 37
  • 52
4

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.

gcbenison
  • 11,723
  • 4
  • 44
  • 82
  • 2
    No it's not. It's really an artifact of the fact that Lisp is dynamically typed (or from a lambda calculus perspective, untyped). The statically typed analogues of Lisp don't have dotted lists because the type of their counterparts to `cons` restricts the second argument to be a list. E.g., in Haskell, we have `(:) :: a -> [a] -> [a]` (the `:` operator takes an `a` and a list of `a` and returns a list of `a`). – Luis Casillas Jan 30 '12 at 23:05
  • 2
    Hey, I disagree with both of you :). It's easy to build a dynamically typed language where cons can only be used when the second element is a proper list. For instance, see the teaching language levels in Racket. This is a bit like the checking associated with the + operator, for instance. + doesn't work on strings, and that's checked when it's applied. – John Clements Jan 31 '12 at 17:30
1

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)))))
Ryan Culpepper
  • 10,495
  • 4
  • 31
  • 30