27 Apr
2010
27 Apr
'10
7:30 p.m.
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.