On Sat, Oct 04, 2008 at 03:01:15PM +0100, Thomas Schilling wrote:

2008/10/1 Stephan Friedrichs :

...

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.