darcs patch: Make toList a member of Foldable
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