Hello,
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. Thanks in advance Stephan [1] using ghc-6.8.3 -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
I think this is covered by the assumed associativity of mappend.
I.e., if `f' is associative, then `foldr = foldl' modulo performance. 2008/10/1 Stephan Friedrichs <[hidden email]>: > Hello, > > 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. > > Thanks in advance > Stephan > > [1] using ghc-6.8.3 > > > -- > > Früher hieß es ja: Ich denke, also bin ich. > Heute weiß man: Es geht auch so. > > - Dieter Nuhr > _______________________________________________ > Libraries mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/libraries > Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
On Sat, Oct 04, 2008 at 03:01:15PM +0100, Thomas Schilling wrote:
> 2008/10/1 Stephan Friedrichs <[hidden email]>: > > 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. _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |