darcs patch: Make toList a member of Foldable

Ross Paterson ross at soi.city.ac.uk
Tue Apr 27 19:30:15 EDT 2010

On Wed, Apr 28, 2010 at 12:21:58AM +0100, Ross Paterson wrote:
> On Wed, Apr 28, 2010 at 12:53:27AM +0200, Eelis van der Weegen wrote:
> > 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?
> The definition in Data.Foldable is
>   toList :: Foldable t => t a -> [a]
>   toList t = build (\ c n -> foldr c n t)
> For lists, this Data.Foldable.foldr should be inlined to Data.List.foldr.

For NonEmptyList this should become

  toList t = build (\ c n -> c h (Data.List.foldr c n t))

I'd expect the rest of the steps to still apply, but these RULES are tricky.

More information about the Libraries mailing list