[Haskell-cafe] 'Associative' order of calling

Tom Ellis tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk
Sun Oct 25 08:33:09 UTC 2015

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`?


More information about the Haskell-Cafe mailing list