Data.Foldable documentation

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Data.Foldable documentation

Stephan Friedrichs-3
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
Reply | Threaded
Open this post in threaded view
|

Re: Data.Foldable documentation

Thomas Schilling-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Data.Foldable documentation

Ross Paterson
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