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