<div dir="ltr">On Wed, Oct 28, 2015 at 7:50 PM, Janis Voigtländer <span dir="ltr"><<a href="mailto:janis.voigtlaender@gmail.com" target="_blank">janis.voigtlaender@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div><span class=""></span>Your message contained lots of category-theory-speak that wasn’t called for.</div></div></blockquote><div><br><br>Wait, what? You're alluding to my mention of F-algebras? <br><br>Now I know that your discussion with Matteo that cited two papers is pertinent and also kinda off on the side. As we both know, those papers go far deeper into CT than F-algebras, which is like, baby stuff in comparison.<br><br>Baby stuff that they are, F-algebras are nice because it's a theory of data where the folds fall out for free. It's a rock solid theory in a sea of nebulous generalizations about fold. That's why I mentioned them.<br><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><span class="">
<blockquote style="margin:1.2em 0px;border-left:4px solid rgb(221,221,221);padding:0px 1em;color:rgb(119,119,119);quotes:none">
<p style="margin:1.2em 0px!important">Question: What is a fold of type “(a -> a -> a) -> [a] -> a” that promises to call its first parameter “associatively”?</p>
<p style="margin:1.2em 0px!important">Answer: It is a fold equivalent to a fold1 (left or right, it doesn’t matter).</p>
</blockquote>
</span><p style="margin:1.2em 0px!important">No, it seems you haven’t understood the answer. At least, that was not the answer.</p></div></div></blockquote><div><br>Well, look. I thought otherwise, but I may be wrong. I frequently am. And if I am wrong, I want to be put right. Let's examine the facts.<br><br>In an earlier response to Tom, you wrote:<br><br>'So, for the special case of non-empty lists, how about expressing the desired property as follows: "The function h must satisfy: for all associative f and all lists xs, it holds that h f xs = foldl1 f xs."'<br><br>I thought impeccable the logic you used to arrive at this.<br><br>Over two eta-contractions, I get h = foldl.<br><br>The folds are monotyped, the lists finite, and so foldl = foldr.<br><br>Putting it all together, finally:<br><br>The property of the fold in question is that it is equivalent to a fold (left or right, it doesn't matter which).<br><br><br><br> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>
<div title="MDH:PGRpdj48ZGl2PiZndDsgJmd0OyBLaW0tRWUsIEkgdGhpbmsgeW91IGFyZSBvdmVyY29tcGxpY2F0
aW5nIHRoaW5nczxicj4mZ3Q7IDxicj4mZ3Q7IE5vLjxicj48YnI+PC9kaXY+WW91ciBtZXNzYWdl
IGNvbnRhaW5lZCBsb3RzIG9mIGNhdGVnb3J5LXRoZW9yeS1zcGVhayB0aGF0IHdhc24ndCBjYWxs
ZWQgZm9yLjxicj48YnI+Jmd0OyBRdWVzdGlvbjogV2hhdCBpcyBhIGZvbGQgb2YgdHlwZSAiKGEg
LSZndDsgYSAtJmd0OyBhKSAtJmd0OyBbYV0gCi0mZ3Q7IGEiIHRoYXQgcHJvbWlzZXMgdG8gY2Fs
bCBpdHMgZmlyc3QgcGFyYW1ldGVyICJhc3NvY2lhdGl2ZWx5Ij88YnI+PGRpdj4mZ3Q7IDxicj48
L2Rpdj4mZ3Q7IEFuc3dlcjogSXQgaXMgYSBmb2xkIGVxdWl2YWxlbnQgdG8gYSBmb2xkMSAobGVm
dCBvciByaWdodCwgaXQgZG9lc24ndCBtYXR0ZXIpLjxicj48YnI+PC9kaXY+Tm8sIGl0IHNlZW1z
IHlvdSBoYXZlbid0IHVuZGVyc3Rvb2QgdGhlIGFuc3dlci4gQXQgbGVhc3QsIHRoYXQgd2FzIG5v
dCB0aGUgYW5zd2VyLjxicj48ZGl2Pjxicj48L2Rpdj4=" style="min-height:0;width:0;max-height:0;max-width:0;overflow:hidden;font-size:0em;padding:0;margin:0"></div></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2015-10-28 13:41 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">On Sun, Oct 25, 2015 at 1:17 PM, Janis Voigtländer <span dir="ltr"><<a href="mailto:janis.voigtlaender@gmail.com" target="_blank">janis.voigtlaender@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div><div>Kim-Ee, I think you are overcomplicating things</div></div></div></div></div></div></div></div></blockquote><div><br></div><div>No.<br><br>Matteo cited a paper on traversables and you added a rejoinder. So it wasn't me who introduced data abstraction.<br><br>Also, OP explicitly asked about a fold "on a set of data". Only later, when requested for an example, did he give lists.<br><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div>In fact, the discussion of "arbitrary data structures" (in this thread in general) distracts a lot from the properties under consideration, and from even first finding out whether they are properties of foldLike or of f in foldLike f.<br><br></div>So, let's specialize. Let's consider only the case of non-empty lists.</div></div></div></div></div></div></blockquote><div><br></div><div>And look at what we have: A definitive answer to OP's question:<br><br></div><div>Question: What is a fold of type "(a -> a -> a) -> [a] -> a" that promises to call its first parameter "associatively"?<br><br></div><div>Answer: It is a fold equivalent to a fold1 (left or right, it doesn't matter).<br><br></div><div>That's nice.<br><br>But is that all we can come up with? Does it really do justice to the original question? Viz.<br><br>"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. Or in
other words, it has the property that it promises to call a function
"associatively" on a set of data?"<br><br></div><div>The challenge becomes:<br><br></div><div>* generalize the result to fearsomely complicated "arbitrary data structures"<br></div><div>* answer the original question in a holistic spirit<br></div><div><br><br></div><div><br> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div> Then, candidate functions for "foldlike functions" will be functions of this type:<br><br></div>foldLike : (a -> a -> a) -> [a] -> a<br><br></div>Here are some candidates (I give only an equation for four element lists in each case, but I assume everyone has enough imagination to see how these could be extended to other lists in an intended way):<br><br>foldLike1 f [a,b,c,d] = [] -- throws away stuff<br>foldLike2 f [a,b,c,d] = f a (f b (f c d)) -- we have all ancountered this one<br>foldLike3 f [a,b,c,d] = f (f (f a b) c) d -- also looks familiar<br>foldLike4 f [a,b,c,d] = f (f a b) (f c d) -- that's a "new" one, but looks good<br></div>foldLike5 f [a,b,c,d] = f a a -- probably not a very popular one<br>foldLike6 f [a,b,c,d] = f (f c a) (f b d) -- a reasonable one, for example there's a Traversable instance that leads to this one; but still, it's not one that Charles would like, I think<br><br></div>So now we can ask which of these satisfy Charles's 1., 2., 3. points. Can't we?<br><br></div>There was:<br><br><div><div><span><div>> 1. Promises to call f on all data (does not have any guarantees on order)<br><br></div></span><div>This is satisfied by foldLike2, foldLike3, foldLike4, and foldLike6, but not by the others.<br></div><span><div><br></div><div>> 2. Promises to call f on all data in order (like a left fold)<br><br></div></span><div>This is satisfied by foldLike3, but not by the others.<br><br></div><span><div>> 3. Promises to call f "associatively" (perhaps can be formalized as an in order break down of the data into tree structures)</div><br></span></div><div>This is satisfied by foldLike2, foldLike3, and foldLike4, but not by the others.<br><br></div><div>Since I am able to tell, for a given foldLike candidate, whether or not it satisfies 3. (for example, I could specifically see that foldLike6 does not satisfy 3., while it does satisfy 1.), it cannot be maintained that 3. has no meaning.<br></div><div><br><div>Note: Nothing in the above makes any assumptions about f. Whether or not f is an associative function is irrelevant for what is asked here.<br></div><div><br><div><div><div><div><br><br></div></div></div></div></div></div></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-25 4:19 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">On Sun, Oct 25, 2015 at 1:12 AM, Janis Voigtländer <span dir="ltr"><<a href="mailto:janis.voigtlaender@gmail.com" target="_blank">janis.voigtlaender@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div>It has already been established in this thread what Charles meant by 3.<br><br></div>He meant that a fold-function that has the property he is after would guarantee that it:<br></div><br>a) takes all the content elements from a data structure, say x1,...,xn,<br><br></div>b) builds an application tree with the to-be-folded, binary operation f in the internal nodes of a binary tree, whose leafs, read from left to right, form exactly the sequence x1,...,xn,<br><br></div>c) evaluates that application tree.<br><br></div></div></div></blockquote><div><br></div><div>Isn't this what Charles meant by his 2nd property:<br><br>> 2. Promises to call f on all data in order (like a left fold)</div><div> <br></div><div>What about his 3rd?<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div></div>Do you agree that what I describe above is a property of a given fold-like function, not of the f handed to that fold-like function?<br></div></div></blockquote><div><br></div><div>Before discussing a property of X, isnt it worth asking what X even means?<br><br></div><div>The folds whose meanings are crystal clear are the arrows out of initial objects in the category of F-algebras.<br><br></div><div>They are crystal clear because they couple as one with the data definition spelled out in full.<br><br></div><div>In the quest for useful generalizations of catamorphisms, that coupling with the data definition continues to be assumed.<br><br></div><div>Observe, for instance:<br><br>> a) takes all the content elements from a data structure, say x1,...,xn,<br><br></div><div>Does a foliar data structure have a canonical flattening out of its leaves? Are there symmetric canonicalizations? How is one selected over the others?<br><br></div><div>Is the meaning of "all" referentially transparent? That turns out to be a subtle point, as this convo shows:<br><br></div><div><a href="http://haskell.1045720.n5.nabble.com/A-Proposed-Law-for-Foldable-tp5765339.html" target="_blank">http://haskell.1045720.n5.nabble.com/A-Proposed-Law-for-Foldable-tp5765339.html</a><br><br></div><div>With the theory of F-algebras, we started with precise notions of data and folds came for free.<br><br></div><div>But data can be overspecified. And also, the folds among swathes of data suggest useful generalizations.<br></div><div><br></div><div>So now, a raft of proto-precise and necessarily psychological notions of Foldable waded in, and since then it's been fun playing sorting games with shape blocks and holes to squeeze them into.<br><br></div><div>Fun is good. It's a stage in the journey to knowledge.<br></div><br><div><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">And do you agree that what I describe above is a property that is weaker than (and so, in particular different from) for example the property "this fold-like function is foldl or foldr".<br></blockquote></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"></blockquote><div><br></div><br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><br></div></div></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-24 19:55 GMT+02: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 Sun, Oct 25, 2015 at 12:42 AM, Matteo Acerbi <span dir="ltr"><<a href="mailto:matteo.acerbi@gmail.com" target="_blank">matteo.acerbi@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 style="font-family:monospace,monospace;display:inline"></div><div style="font-family:monospace,monospace;display:inline">For what concerns question 3, I didn't understand the idea of calling a function "associatively".</div></blockquote></div><br></div><div class="gmail_extra">This. Associativity is a property of binary operators. It's not a property of the catamorphism 'calling' on a given binary operator.<br><br></div><div class="gmail_extra">Also, when Charles writes: "Then it goes on to use f in "thisFold f [0,1,2]" like "f (1 (f 0 2))""<br><br></div><div class="gmail_extra">commutativity appears to raise its head.<span><font color="#888888"><br> </font></span></div><span><font color="#888888"><div class="gmail_extra"><br clear="all"><div><div>-- Kim-Ee</div></div>
</div></font></span></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>