How lazy is DData.Seq?
jyp_7 at yahoo.com
Mon May 10 15:33:55 EDT 2004
--- 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
> > Anyways, 'toList' will still be O(m) where m =
> number of subtrees. Moreover,
> > I hardly expect more that O(n) empty subtrees in a
> 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
Yet, toList might be evaluated more than once for a
Do you Yahoo!?
Win a $20,000 Career Makeover at Yahoo! HotJobs
More information about the Libraries