[Haskell-cafe] 'Associative' order of calling
Janis Voigtländer
janis.voigtlaender at gmail.com
Sun Oct 25 09:06:00 UTC 2015
> 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?
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."
Chris's original question would then be whether there is a name for that
property. And how to generalize the property to other types than non-empty
lists (for example, ones for which it is not clear what "left" and "right"
mean) would be a separate concern.
2015-10-25 9:33 GMT+01:00 Tom Ellis <
tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk>:
> On Sun, Oct 25, 2015 at 06:58:23AM +0100, Janis Voigtländer wrote:
> > I don't think I see what you are getting at, Tom. Let's consider the
> > special case of non-empty lists. One fold-like function that has the
> > property I think Charles meant by 3., would be one that works as follows:
> >
> > foldBalanced :: (a -> a -> a) -> [a] -> a
> > foldBalanced f [x] = x
> > foldBalanced f [x,y] = f x y
> > foldBalanced f [x,y,z] = f x (f y z)
> > foldBalanced f [x,y,z,u] = f (f x y) (f z u)
> > ... -- I hope you can see the pattern (building f-application trees that
> > are as balanced as possible)
> >
> > I don't see how this function can be written as g . foldl f z for some g
> > and z.
>
> Ah, thank you Janis. I think you are clarifying for me the meaning of
> 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`?
>
> Tom
> _______________________________________________
> 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/20151025/ef14af27/attachment.html>
More information about the Haskell-Cafe
mailing list