How lazy is DData.Seq?
jyp_7 at yahoo.com
Mon May 10 07:56:08 EDT 2004
--- 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.
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