[Haskell-cafe] 'Associative' order of calling

Kim-Ee Yeoh ky3 at atamo.com
Tue Nov 3 00:55:38 UTC 2015

On Thu, Oct 29, 2015 at 1:27 PM, Janis Voigtländer <
janis.voigtlaender at gmail.com> wrote:

> Are you sure you have read and respected all the forall-quantifiers in
> there?
> The statement "for all associative f and all lists xs, it holds that h f
> xs = foldl1 f xs" is *not* equivalent to the statement "for all f and all
> lists xs, it holds that h f xs = foldl1 f xs". The latter statement is
> equivalent (via eta-contractions) to "h = foldl", but the former isn't.
> Do I have to give a specific h to make this clearer? One which satisfies
> the first statement but is not equivalent to foldl or foldr. Actually, one
> was given already earlier in the conversation, to exactly the purpose of
> illuminating this whole point.

So you're saying:

"The property of the fold in question is that it's equivalent to a fold
(left or right, it's all one) __on the space of associative binary

That's not too far off is it?

I deliberately abbreviated for three reasons.

The first is that restriction to associative binary operators is inherent
in the original question. Recall: "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."

The second reason is that it summarizes the result into an easy take-away.

Lastly, the fuller answer can be worked out once we throw a glance at the
obviousness that foldl and foldr cannot be equal on the space of
non-associative binary operators.

-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151103/9ece2e03/attachment.html>

More information about the Haskell-Cafe mailing list