darcs patch: Make toList a member of Foldable
ross at soi.city.ac.uk
Tue Apr 27 19:21:58 EDT 2010
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.
(Hmm, does the INLINE of toList block that?)
If this build isn't eliminated by some outer foldr, it should eventually
unfold its definition:
build g = g (:) 
toList t = foldr (:)  t
and the rule "foldr/id" should reduce that to
toList t = t
If this isn't happening, it needs fixing.
More information about the Libraries