[Haskell-cafe] 'Associative' order of calling

[Janis Voigtländer]

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 at gmail.com>:

> On Fri, Oct 23, 2015 at 6:07 PM, Charles Durham <ratzes at 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151024/a2a68285/attachment.html>