[Haskell-cafe] 'Associative' order of calling

[Janis Voigtländer]

2015-11-03 1:55 GMT+01:00 Kim-Ee Yeoh <ky3 at atamo.com>:

>
> 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
> operators.__"
>
> That's not too far off is it?
>

It is what was meant, yes. With that part in "__ ... __".


> 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."
>

I don't actually see how that question has an inherent restriction of the
kind you read into it, that we will never have to even think about what the
function does if called with a non-associative operator. On the contrary.
Saying that, paraphrasing, "*only* when you call the function with an
associative operator, something specific holds", does for sure imply that
to work out the condition we have to *also* consider what happens for
non-associative operators. Otherwise the "only" is pointless.

And in particular in the early messages of the thread, there was discussion
and confusion about whether what is sought here is a property of f or of h
or of both. So silently making assumptions about one of them seems not a
good idea to me. And even later in the thread we have again seen criticism
like "but this can't be expressed at all, because Haskell's type system is
not strong enough to capture associativity of operators". That criticism
does apply when sweeping "on the space of associative binary operators"
under the rug as if we could really say "extensional equality of functions"
and mean "the functions must give equal results when called on associative
operators". (If, but only if, we could express associativity in types, we
could write down a function type whose meaning of extensionality agrees
with what is claimed.)

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

Well, "easy" can often be "subtly wrong or at least confusing if glossing
over the full meaning".


> 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.
>

Yes, the correct answer can be worked out with some thinking.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151103/c3256b38/attachment-0001.html>