Re: lists

[david carlton <carlton@husc.harvard.edu>]

On Mon, 19 Jul 93 10:30:13 CDT, Andrew Wright <wright@cs.rice.edu> said:

> The R4RS has a section that carefully describes a "list" as something
> that has finite length and ends in nil, ie., a proper list.

> member is specified as taking a list for its second argument, so
> the usual definition:

>   (define member
>     (lambda (x l)
>       (cond [(null? l) #f]
>             [(equal? x (car l)) l]
>             [else (member x (cdr l))])))

> is too liberal, since (member 'a '(a . 5)) works.

It also accepts infinite lists.

> What is the intended interpretation of "list" as an argument type
> specification for the various library functions?  My guess is that
> an interpretation may provide the restrictive implementation, but is
> free to provide the more liberal version.

It would be bad for this not to be the case, since that would require
procedures taking lists as arguments to traverse the entire list,
which means that the time that, say, list-tail takes would be linear
in the length of the list rather than the second argument.

> If so, this should be said explicitly.

It doesn't say that an error should be signalled, so that is good
enough.  In fact, in the section on error situations and unspecified
behaviour, there is the following text:

+ For example, it is an error for a procedure to be passed an
+ argument that the procedure is not explicitly specified to handle,
+ even though such domain errors are seldom mentioned in this report.
+ Implementations may extend a procedure's domain of definition to
+ include such arguments.

> The description of list-tail should also be fixed.

To do what?  Be more restrictive but slower and less clean?
Personally, I rather like it the way that it is.

david carlton
carlton@husc.harvard.edu