<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">2015-11-03 1:55 GMT+01:00 Kim-Ee Yeoh <span dir="ltr"><<a href="mailto:ky3@atamo.com" target="_blank">ky3@atamo.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Oct 29, 2015 at 1:27 PM, Janis Voigtländer <span dir="ltr"><<a href="mailto:janis.voigtlaender@gmail.com" target="_blank">janis.voigtlaender@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><span style="white-space:pre-wrap">Are you sure you have read and respected all the forall-quantifiers in there?<br><br></span></div><span style="white-space:pre-wrap">The statement "</span><span style="white-space:pre-wrap">for all associative f and all lists xs, it holds that h f xs = foldl1 f xs" is *not* equivalent to the statement "</span><span style="white-space:pre-wrap">for all f and all lists xs, it holds that h f xs = foldl1 f xs". The latter statement is equivalent (via eta-contractions) to "</span><span style="white-space:pre-wrap">h = foldl", but the former isn't.<br><br></span></div><span style="white-space:pre-wrap">Do I have to give a specific h to make this clearer? One which satisfies the first statement but is not equivalent to foldl or foldr. Actually, one was given already earlier in the conversation, to exactly the purpose of illuminating this whole point.</span></blockquote></div><br></div><div class="gmail_extra">So you're saying:<br><br>"The property of the fold in question is that it's equivalent to a fold (left or right, it's all one) __on the space of associative binary operators.__"<br><br>That's not too far off is it?<br></div></div></blockquote><div><br></div><div>It is what was meant, yes. With that part in "__ ... __".<br> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra">I deliberately abbreviated for three reasons.<br><br>The first is that restriction to associative binary operators is inherent in the original question. Recall: "Is there a name for a fold that promises to call a function such that 
only an associative function will always return the same result."<br></div></div></blockquote><div><br></div><div>I don't actually see how that question has an inherent restriction of the kind you read into it, that we will never have to even think about what the function does if called with a non-associative operator. On the contrary. Saying that, paraphrasing, "*only* when you call the function with an associative operator, something specific holds", does for sure imply that to work out the condition we have to *also* consider what happens for non-associative operators. Otherwise the "only" is pointless.<br><br></div><div>And in particular in the early messages of the thread, there was discussion and confusion about whether what is sought here is a property of f or of h or of both. So silently making assumptions about one of them seems not a good idea to me. And even later in the thread we have again seen criticism like "but this can't be expressed at all, because Haskell's type system is not strong enough to capture associativity of operators". That criticism does apply when sweeping "on the space of associative binary operators" under the rug as if we could really say "extensional equality of functions" and mean "the functions must give equal results when called on associative operators". (If, but only if, we could express associativity in types, we could write down a function type whose meaning of extensionality agrees with what is claimed.)<br></div><br><div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra">The second reason is that it summarizes the result into an easy take-away.<br></div></div></blockquote><div><br></div><div>Well, "easy" can often be "subtly wrong or at least confusing if glossing over the full meaning".<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra">Lastly, the fuller answer can be worked out once we throw a glance at the obviousness that foldl and foldr cannot be equal on the space of non-associative binary operators.<span><font color="#888888"><br></font></span></div></div></blockquote><div><br></div><div>Yes, the correct answer can be worked out with some thinking.<br></div><br></div></div></div>