<div dir="ltr"><div>The "unitarity" and "linearity" laws are indeed relevant for Charles's question. But they won't give him his 2. or 3. point. They will exactly entail the property he mentions in his 1. point: that each data element is touched exactly once (whereas all permutations of the order will still be legal).<br><br></div>For proof of that, see <a href="http://dx.doi.org/10.1145/2503778.2503781">http://dx.doi.org/10.1145/2503778.2503781</a>, which establishes as fact the relevant conjecture from Jaskelioff & Rypacek's paper.<br></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-24 10:29 GMT+02:00 Matteo Acerbi <span dir="ltr"><<a href="mailto:matteo.acerbi@gmail.com" target="_blank">matteo.acerbi@gmail.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">On Fri, Oct 23, 2015 at 6:07 PM, Charles Durham <span dir="ltr"><<a href="mailto:ratzes@gmail.com" target="_blank">ratzes@gmail.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">I can think of a few properties that folds can honor:<div><br></div><div>1. Promises to call f on all data (does not have any guarantees on order)</div><div>2. Promises to call f on all data in order (like a left fold)</div><div>3. Promises to call f "associatively" (perhaps can be formalized as an in order break down of the data into tree structures)</div></div></blockquote><div><br><div class="gmail_default" style="font-family:monospace,monospace;display:inline">For what concerns traversable functors, traversals enjoy properties of "unitarity" and "linearity" which *might* entail what you are interested in:<br><br>M. Jaskelioff, O. Rypacek - An Investigation of the Laws of Traversals<br><a href="http://arxiv.org/abs/1202.2919" target="_blank">http://arxiv.org/abs/1202.2919</a><br><br></div><div class="gmail_default" style="font-family:monospace,monospace;display:inline">I have never gone through the details of that very interesting paper: the analysis in section 4 gives some intuition, though.<br><br></div><div class="gmail_default" style="font-family:monospace,monospace;display:inline">I hope this is related to your questions.<br></div><div class="gmail_default" style="font-family:monospace,monospace;display:inline"><br></div><div class="gmail_default" style="font-family:monospace,monospace;display:inline">Cheers,<br></div><div class="gmail_default" style="font-family:monospace,monospace;display:inline">Matteo<br></div></div></div></div></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>