[Haskell-cafe] 'Associative' order of calling

[Tom Ellis]

On Sun, Oct 25, 2015 at 10:06:00AM +0100, Janis Voigtländer wrote:
> > Chris's original question:
> >
> > 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?
> >
> > So is the property that the function (h, say) satifises `h f = g . foldl
> f z`
> > for all associative `f`?
> 
> That makes a lot of sense, Tom, as a property of h to satisfy, while
> quantifying over associative f inside that property. (Instead of as an
> equation-definition for h in terms of foldl.)
> 
> I now wonder why any g other than the identity function should be
> necessary, though. And for the type of non-empty lists, one should also be
> able to get rid of the z?

Chris said "Is there a name for a fold", which I originally misunderstood as
"Is there a name for a function".  I'm not quite sure how to define "fold",
but if it agrees with your definition of "fold" then your characterization
below should be fine.

> So, for the special case of non-empty lists, how about expressing the
> desired property as follows: "The function h must satisfy: for all
> associative f and all lists xs, it holds that h f xs = foldl1 f xs."

Tom