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