<div dir="ltr"><div><div><div><span style="white-space:pre">> Chris's original question:<br>> <br>>      Is there a name for a fold that promises to call a function such that only<br>>      an associative function will always return the same result. Or in other<br>>      words, it has the property that it promises to call a function<br>>      "associatively" on a set of data?<br>> <br>> So is the property that the function (h, say) satifises `h f = g . foldl f z`<br>> for all associative `f`?<br><br></span></div><span style="white-space:pre">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.)<br><br></span></div><span style="white-space:pre">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?<br><br></span></div><span style="white-space:pre">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."</span><br><div><div><span style="white-space:pre"></span><div><span style="white-space:pre"><br></span></div><div><span style="white-space:pre">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.<br></span></div><div><span style="white-space:pre"><br></span></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-25 9:33 GMT+01:00 Tom Ellis <span dir="ltr"><<a href="mailto:tom-lists-haskell-cafe-2013@jaguarpaw.co.uk" target="_blank">tom-lists-haskell-cafe-2013@jaguarpaw.co.uk</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Oct 25, 2015 at 06:58:23AM +0100, Janis Voigtländer wrote:<br>
> I don't think I see what you are getting at, Tom. Let's consider the<br>
> special case of non-empty lists. One fold-like function that has the<br>
> property I think Charles meant by 3., would be one that works as follows:<br>
><br>
> foldBalanced :: (a -> a -> a) -> [a] -> a<br>
> foldBalanced f [x] = x<br>
> foldBalanced f [x,y] = f x y<br>
> foldBalanced f [x,y,z] = f x (f y z)<br>
> foldBalanced f [x,y,z,u] = f (f x y) (f z u)<br>
> ... -- I hope you can see the pattern (building f-application trees that<br>
> are as balanced as possible)<br>
><br>
> I don't see how this function can be written as g . foldl f z for some g<br>
> and z.<br>
<br>
Ah, thank you Janis. I think you are clarifying for me the meaning of<br>
Chris's original question:<br>
<br>
     Is there a name for a fold that promises to call a function such that only<br>
     an associative function will always return the same result. Or in other<br>
     words, it has the property that it promises to call a function<br>
     "associatively" on a set of data?<br>
<br>
So is the property that the function (h, say) satifises `h f = g . foldl f z`<br>
for all associative `f`?<br>
<br>
Tom<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br></div>