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

For proof of that, see http://dx.doi.org/10.1145/2503778.2503781, which establishes as fact the relevant conjecture from Jaskelioff & Rypacek's paper.

2015-10-24 10:29 GMT+02:00 Matteo Acerbi <matteo.acerbi@gmail.com>:
On Fri, Oct 23, 2015 at 6:07 PM, Charles Durham <ratzes@gmail.com> wrote:
I can think of a few properties that folds can honor:

1. Promises to call f on all data (does not have any guarantees on order)
2. Promises to call f on all data in order (like a left fold)
3. Promises to call f "associatively" (perhaps can be formalized as an in order break down of the data into tree structures)

For what concerns traversable functors, traversals enjoy properties of "unitarity" and "linearity" which *might* entail what you are interested in:

M. Jaskelioff, O. Rypacek - An Investigation of the Laws of Traversals
http://arxiv.org/abs/1202.2919

I have never gone through the details of that very interesting paper: the analysis in section 4 gives some intuition, though.

I hope this is related to your questions.

Cheers,
Matteo

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe