<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>