[plt-scheme] The role of proper and improper lists?

On Jan 24, 2008, at 10:24 PM, Grant Rettke wrote:

> An improper list is *not* terminated with the empty list, a proper
> list is terminated:
>
> (cons 1 2)
>
> versus
>
> (cons 1 (cons 2 '()))
>
> Where/when/why does this matter?

As Marco mentioned, it matters when you want to use standard library  
functions that expect proper lists.

It also matters when you have lists of lists.

It is not too hard to hack up code that could deal with either of the  
two cases you list above.

But the real problem comes when you want to write code that processes a
[Listof [Listof Integer]], like the following:

(cons (cons 1  (cons 2  (cons 3  (cons 4  '())))
  (cons (cons 5  (cons 6  (cons 7  (cons 8  '())))
   (cons (cons 9  (cons 10 (cons 11 (cons 12 '())))
    '())))

Here, the distinction introduced by terminating the list properly with  
a '() is crucial, because we want to distinguish the three element  
list above (where each element is a four element list of integers)  
from the *six* element list below:

(cons (cons 1  (cons 2  (cons 3  (cons 4  '())))
  (cons (cons 5  (cons 6  (cons 7  (cons 8  '())))
   (cons 9
    (cons 10
     (cons 11
      (cons 12
       '()))))))

This six element list is neither a [Listof Integer] nor a [Listof  
[Listof Integer]]; it is heterogeneous, which is not inherently wrong,  
but does set off alarm bells in my mind.

-Felix