How lazy is DData.Seq?

[JP Bernardy]

--- Wolfgang Jeltsch <wolfgang at jeltsch.net> wrote:
> Am Montag, 10. Mai 2004 15:56 schrieb JP Bernardy:
> > --- Simon Marlow <simonmar at microsoft.com> wrote:
> > > Ross's point about requiring append to be strict
> in order to guarantee
> > > O(n) toList is a good one.  In fact, the current
> implementation isn't
> > > quite correct: either fromList should be strict,
> or append should check
> > > for an empty Many constructor.
> >
> > That's what exists in the current published
> version (on my "web page"):
> > fromList guarantees that the Many constructor
> never has [] as argument.
> 
> Is it right that making this guarantee results in
> the strictness I would like 
> to avoid?

To be precise:

Making fromList guarantee that "the Many constructor
never has [] as argument" is a part of an
implementation that gives the O(n) behaviour for
toList. It does not make append strict.

A strict append is necessary, in any case, for the
O(n) behaviour.


> > Anyways, 'toList' will still be O(m) where m =
> number of subtrees. Moreover,
> > I hardly expect more that O(n) empty subtrees in a
> sequence.
> 
> It's theoretically possible that m is much larger
> than n.  But since you need 
> at least O(m) time to construct a Seq with m
> subtrees¹) the total time of Seq 
> construction plus conversion is asymptotically the
> same as without full 
> lazyness.

Yet, toList might be evaluated more than once for a
given sequence.

Cheers,
JP.


	
		
__________________________________
Do you Yahoo!?
Win a $20,000 Career Makeover at Yahoo! HotJobs  
http://hotjobs.sweepstakes.yahoo.com/careermakeover