[plt-scheme] PLT4 expectations

Both in space and in time I think. One list traversal for the length is 
probably faster than keeping track of the length of the list and all its 
cdrs all the way through. Moreover, for many lists, the length is never 
asked for. It may spare time when length is frequently called with the same 
list, but I think that rarely occurs and imho could be a reason for 
suspicion with regard to the capabilities of the programmer.
Jos

----- Original Message ----- 
From: "Matthew Flatt" <mflatt at cs.utah.edu>
To: "Doug Orleans" <dougorleans at gmail.com>
Cc: "PLT-Scheme Mailing List" <plt-scheme at list.cs.brown.edu>
Sent: Tuesday, March 11, 2008 8:46 PM
Subject: Re: [plt-scheme] PLT4 expectations


> At Tue, 11 Mar 2008 13:59:33 -0400, Doug Orleans wrote:
>> Matthew Flatt writes:
>>  > At Tue, 11 Mar 2008 01:01:08 -0400, Doug Orleans wrote:
>>  > > Matthew Flatt writes:
>>  > >  > At Mon, 10 Mar 2008 14:34:49 +0000, "Paulo J. Matos" wrote:
>>  > >  > > The idea of PLT4 creating by default immutable pairs and the 
>> so,
>> means
>>  > >  > > that it also opens the possibility for far more and better
>>  > >  > > optimizations in the compiler, right?
>>  > >  >
>>  > >  > I doubt that there are many new optimization opportunities that 
>> matter
>>  > >  > in practice.
>>  > >
>>  > > Well, you could make "list?" be O(1) instead of O(n), at a cost of 
>> one
>>  > > bit per cons cell.
>>  >
>>  > Yes, `list?' is currently amortized constant time.
>>
>> That's great!  I instinctively avoid "list?" (and <list> specializers
>> in Swindle), but now I will stop being afraid.
>>
>> How about "length" and "last"?  Or would those be too expensive in space?
>
> Yes, I think that would be too expensive.
>
> Matthew
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme