Re: darcs patch: Make toList a member of Foldable

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 (:) [] giving toList t = foldr (:) [] t and the rule "foldr/id" should reduce that to toList t = t If this isn't happening, it needs fixing.