Re: [Scheme-reports] Query - Pairs and Lists
Per Bothner 04 Mar 2012 20:11 UTC
On 03/04/2012 08:43 AM, Ray Dillinger wrote:
> Passing a structure which is not a list to a procedure that
> is specified to work on lists gives a non-specified result.
>
> Implentations may signal an error, but the cost of doing so
> (especially in the case where there is no error) would be
> high.
>
> So high, in fact, that *guaranteeing* a signaled error would
> invalidate the programmer's model of the time complexity
> of the code.
You could have a bit or separate typecode for non-list cons
cells - for example LIST_PAIR vs NON_LIST_PAIR. Cons creates
a LIST_PAIR if the cdr is '() or a LIST_PAIR, and creates a
NON_LIST_PAIR otherwise. set-cdr! checks the new cdr if it
is a NON_LIST_PAIR *or* if the set-cdr! would create a cycle.
In that case checking for a pure list is O(1). Only set-cdr!
becomes order-of-magnitude slower, but it's not a function
we want to encourage use of anyway.
Note that NON_LIST_PAIR is conservative: You might create
a non-list, and then a future set-cdr! might change it back
to a true list. One might accept that as OK (i.e. false
raise of an exception), or just use NON_LIST_PAIR as an indicator
that a slow scan is needed. For simplicity I' be tempted to
say that once a pair is a NON_LIST_PAIR it is forever tainted.
But I'm not sure this is all worth it, though it would be
nice to have list? be an inexpensive type-check. In that case
I'd be tempted to go further: Have two kinds of cons operator:
cons creates a LIST_PAIR *and* makes the cdr immutable;
impure-cons creates a NON_LIST_PAIR with a mutable cdr. Still,
that's a big departure from tradition.
--
--Per Bothner
per@bothner.com http://per.bothner.com/
_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports