[Haskell-cafe] Haskell's "historical futurism" needs better writing, not better tools

[Keith]

When you're writing generically for Foldable, if you want consistent big-O performance, use `foldMap` or `foldMap'`to project to a Monoid that is ideal for how you want to consume the structure, and suck up the larger constant factors.
If you want the best performance for any structure, use the specialized methods (`sum`, `elem`, &c.).
And if you're consuming the structure in an intrinsically biased way, use an intrinsically biased fold.
-- Keith
Sent from my phone with K-9 Mail.

On 1 October 2021 09:52:53 UTC, Ben Franksen <ben.franksen at online.de> wrote:
>Am 01.10.21 um 03:14 schrieb Viktor Dukhovni:
>> On Fri, Oct 01, 2021 at 02:40:49AM +0200, Ben Franksen wrote:
>>> They define semantics in a semi-formal notation, which I find succinct
>>> and very intuitive. This can be easily generalized to Foldable via
>>> 'toList'. Indeed, there is almost nothing about Foldable that cannot be
>>> understood once you understand Data.List and the toList method. Even
>>> foldMap is (semantically) just (***):
>> 
>> 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?
>
>This is a general problem with all kinds of generic "container" 
>classes/interfaces, and not limited to Haskell: performance 
>characteristics of methods will vary widely depending on the 
>implementation. In Haskell this includes semantics insofar as bottom / 
>infinite structures are concerned.
>
>Documenting the API /itself/ can go only so far before becoming a manual 
>enumeration of all possible implementations one can think of or happens 
>to know about. This clearly doesn't scale, so it would be better to 
>leave it unspecified and attach such documentation to the instances instead.
>
>It would help if rendering of instance docs in haddock were improved (as 
>sub-paragraph under the instance instead of to the right of it).
>
>> And it is perhaps worth asking whether you feel you still have anything
>> you'd like to learn about Foldable, for if not, perhaps the
>> documentation is not for you, and that's fine...
>
>I may have earned this remark with the tone of my critique ;-) In case 
>it came over as condescending, please accept my apologies.
>
>>> In fact all class methods have simple semantic definitions in terms of
>>> the same named functions from Data.List via 'toList'.
>> 
>> But performance may differ radically, and `toList` may diverge for
>> `snocList` when infinite on the left, though that's a rather
>> pathological example.
>>
>>> Expectations of runtime cost should be either explicitly stated in the
>>> docs for each method or left out.
>> 
>> That's not enough if users can't reason about the available choices or
>> don't know how to implement performant instances.
>
>The truth is (and that is what the docs imply but fail to make explicit 
>as that would be too embarrasing): you *cannot* reason about these 
>things. If the implementation (instance) is free to choose whether 
>foldr or foldl is the "natural" fold, then how can I make an informed 
>choice between them for an arbitrary Foldable?
>
>If we were to define the semantics in terms of 'toList', then we would 
>acknowledge that Foldable is biased in the same direction as lists are, 
>so behavior would no longer be implementation defined and could be 
>easily reasoned about.
>
>>  Function synopses
>> rarely provide enough room for more than a cursory description and
>> a few examples.  That's not their role.  This is why Unix manpages
>> have both a SYNOPSIS and a DESCRIPTION section.
>> 
>> I am quite open to improved language in the overview, and less open to
>> the idea that it is just baggage to throw overboard.  In particular,
>> I've had positive feedback on the material, despite perhaps overly
>> turgid prose in some places.  Please help to make it crisp.
>> 
>> I find absence of overview (DESCRIPTION if you like) sections in many a
>> non-trivial Haskell library to be quite a barrier to working with the
>> library, the synopses alone are rarely enough for my needs.
>
>I agree. I do like (not too verbose) introduction of concepts when 
>reading docs of a new module. See below for a proposal.
>
>>> I may be wrong but it looks to me as if this could be derived by adding
>>> one more method 'fromList' that is required to be left inverse of 'toList':
>>>
>>>     fromList :: Foldable a => [a] -> t a
>>>     fromList . toList = id
>> 
>> This is roughly the sort of thing one can do with Traversable (recover
>> the structure from its spine and element list, but not its element list
>> alone).  The point is that various non-linear (e.g. tree-like)
>> structures with the same element order have distinct "spines".
>[...]
>>> Is there a sensible (useful, lawful) Foldable instance which has no
>>> 'fromList'?
>> 
>> Sure, any tree-like structure where shape is not implied by the element
>> list alone.
>
>Sorry, you are right, of course. I wasn't thinking clearly.
>
>Regarding me helping to improve the docs: I have made concrete proposals 
>to re-word the descriptions. But I really think that a large part of the 
>documentation you added comes down to saying:
>
>"""
>As specified, this class is mostly useless, since it does not allow you 
>to reason about the choice of methods (e.g. 'foldr' vs. 'foldl') to use 
>when working with a generic Foldable container. To make this choice, you 
>have to make assumptions about whether it is left-leaning (like lists) 
>or right-leaning (like snoc-lists) or neither (unbiased). The usual 
>assumption is that it is right-leaning or unbiased. This means that all 
>methods can be considered as being defined, semantically, using 'toList' 
>and the corresponding function with the same name from Data.List. (For 
>fold and foldMap, see their default definitions).
>
>If you can assume the element type is a Monoid, you can get away by 
>using only the unbiased functions 'fold' and 'foldMap'. This leaves the 
>choice of implementation strategy to the container (instance).
>"""
>
>Cheers
>Ben
>-- 
>I would rather have questions that cannot be answered, than answers that
>cannot be questioned.  -- Richard Feynman
>
>
>_______________________________________________
>Haskell-Cafe mailing list
>To (un)subscribe, modify options or view archives go to:
>http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20211001/54dc2347/attachment.html>