How lazy is DData.Seq?
wolfgang at jeltsch.net
Mon May 10 22:46:48 EDT 2004
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
> 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
¹) Well, exceptions could be cases like fix ( `append`) which might be
constructable in constant time.
More information about the Libraries