darcs patch: Make toList a member of Foldable

Ross Paterson 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 mailing list