How lazy is DData.Seq?

JP Bernardy jyp_7 at
Mon May 10 07:56:08 EDT 2004

--- Simon Marlow <simonmar at> 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.

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. 

So, it is trading off efficiency here for efficiency
there. I suspect most haskellers would intuitively
expect 'append' to be lazy, so I let myself be
convinced by Wolfgang argument. Please let me know if
I am wrong.


Do you Yahoo!?
Win a $20,000 Career Makeover at Yahoo! HotJobs 

More information about the Libraries mailing list