Data.Foldable documentation

[Ross Paterson]

On Sat, Oct 04, 2008 at 03:01:15PM +0100, Thomas Schilling wrote:
> 2008/10/1 Stephan Friedrichs <deduktionstheorem at web.de>:
> > I've got a suggestion for the documentation of the Data.Foldable module. The
> > documentation [1] does not say anything about the order in which the
> > elements are folded. But as far as I understand, the order in which the
> > elements are traversed (i. e. the result of Data.Foldable.toList) has to bee
> > deterministic. The documentation of the Foldable class IMHO should provide a
> > clear statement about that.
> >
> > Example: I implemented a heap that internally uses a tree of elements. It
> > uses a tree to store the elements, but two heaps might be equal (contain the
> > same elements) and still be represented by different trees. Then
> >
> > instance Foldable (Heap p) where
> >    foldMap _ Empty          = mempty
> >    foldMap f (Tree _ x l r) = foldMap f l `mappend` f x `mappend` foldMap f r
> >
> > is a bug which is not indicated by the documentation.
>
> I think this is covered by the assumed associativity of mappend.
> I.e., if `f' is associative, then `foldr = foldl' modulo performance.

No, there's a bug in the documentation here (and in Data.Traversable):
it actually suggests the implementation that is incorrect for Heap.
The grouping doesn't matter, thanks to associativity, but the sequence
in which the elements are visited does.  In the heap case foldMap should
process the entries in priority order, and traverse can't be done without
rebuilding the heap.  Any other sequence would break the abstraction.