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