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