[Haskell-cafe] Improving the docs (specifically Data.Foldable)

[Ben Franksen]

Am 01.10.21 um 19:43 schrieb Viktor Dukhovni:
> On Fri, Oct 01, 2021 at 11:52:53AM +0200, Ben Franksen wrote:
> 
>>> Well a balanced Tree can have an efficient corecursive foldl, or a
>>> performant 'foldr`', and Sets can know their size statically, and `elem`
>>> runs in linear time even in structures that potentially support faster
>>> search.
>>
>> All true, and I think it is important to document these things. The
>> question is: where?
> 
> I disagree that everything one should know about Data.Foldable is
> adequately described in Data.List.  At least not without a new overview
> for Data.List that would cover some of the same ground in that
> specialised context, and could then be imported by reference.
> 
> A reader who wants to better understand folds should learn the
> difference between strict reduction and corecursion, and certainly
> Data.List is not the best place to discuss tips for construction of
> Foldable instances.

I already admitted elsewhere that my initial position (reduce semantics 
to that of lists) was too idealistic. My remark above was about 
attaching the documentation of runtime behaviors for specific instances 
to those instances.

> But ultimately one should understand why foldl',

For lists this is explained in Data.List (though perhaps could use a bit 
of elaboration). For the general case, as mention before by me and 
others, this cannot be answered in general unless you know which 
Foldable you are dealing with or at least make certain assumptions about 
how instances are implemented.

> how to define
> instances, 

How do I define Foldable for snoc-lists? There are two choices:

- Isomorphic to that for lists, i.e. from right to left, to conform to
   common expectations about runtime/bottom behavior for the left/right
   folds?
- Or from left to right, such that foldr is problematic and foldr' the
   recommended one?

> why `elem` is stuck doing linear lookup for `Set`, ...

Agreed, the docs should definitely mentioned that neither `elem` nor in 
fact any other method can be better than linear.

> Different readers will come to the documentation for different needs,

By all means, add advice for writing instances (under a heading that 
says so). However, I claim that the vast majority of readers will want 
to know how to use the class methods in their code or understand why 
some code they try to understand uses a specific method. This is what 
the bulk of the docs should be about.

Unfortunately there doesn't seem to be consensus in the community about 
the general semantics of the left/right associative folds. Contributing 
to the docs makes no sense for me until these questions are resolved.

Cheers
Ben
-- 
I would rather have questions that cannot be answered, than answers that
cannot be questioned.  -- Richard Feynman