[Haskell-cafe] 'Associative' order of calling

[Francesco Ariis]

On Fri, Oct 23, 2015 at 05:12:06PM +0100, Tom Ellis wrote:
> On Fri, Oct 23, 2015 at 12:07:57PM -0400, Charles Durham 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)
> > 
> > I'm assuming at least #1 has a well known name (something completeness?)
> 
> 2. doesn't have any meaning in a pure language, I think.  What would it mean
> to call f on data out of order?

He gave an example in his previous email:

On Fri, Oct 23, 2015 at 11:45:13AM -0400, Charles Durham wrote:
> Let's say you have a function "thisFold :: (a -> a -> a) -> [a] -> a"
>
> and it says that the function 'f' passed in must be associative.
>
> Then it goes on to use f in "thisFold f [0,1,2]" like "f (1 (f 0 2))".
> Obviously f is still associative, but 'thisFold' did not call f
> 'associatively' on the data.

I guess it boils down to "toList has to make sense". Which for every
Foldable instance I can think of does, but it's not really a property,
rather what the instance wants to capture.