gmane.comp.lang.haskell.libraries

Data.Foldable documentation

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.

(Continue reading)

headers

Thomas Schilling | 4 Oct 16:01

Re: Data.Foldable documentation

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 <deduktionstheorem <at> web.de>:
> 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
>
>

(Continue reading)

headers

Ross Paterson | 4 Oct 16:25

Re: Data.Foldable documentation

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.