darcs patch: Make toList a member of Foldable

Eelis van der Weegen eelis at eelis.net
Tue Apr 27 18:53:27 EDT 2010

On 2010-04-28 00:37, Ross Paterson wrote:
> The instance for NonEmpty should be
>   instance Foldable NonEmpty where
>     foldr f x (NonEmpty h t) = f h (foldr f x t)
> which would then rely on the optimization of the [] instance.

Even with such an optimal foldr, the generic toList would still
reconstruct the whole list, which would still be O(n) instead of O(1), no?

More information about the Libraries mailing list