27 Apr
2010
27 Apr
'10
6:53 p.m.
On 2010-04-28 00:37, Ross Paterson wrote:
The instance for NonEmpty should be
instance Foldable NonEmpty where foldr f x (NonEmpty h t) = f h (foldr f x t)
which would then rely on the optimization of the [] instance.
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?