[Haskell-cafe] 'Associative' order of calling

[Janis Voigtländer]

There is no point in trying to understand the concept from the name
'calling "associatively"' here. The "-signs around that word were there
precisely because the OP didn't know what to call this. Also, nobody is
trying to encode associativity in the type or anything like that.

What the OP was essentially asking about (as I understand) was:

How do I express (and how do I name) the property X of a fold-like
function, whose (X's) intuitive meaning is: The fold-like function under
consideration takes elements x1,...,xn from a data-structure in
left-to-right order (so, let's assume the data structure is actually a
list, so that there can be no doubt about what left-to-right means) and
then builds a well-bracketed application expression with f on those
elements, where the order of the x1,...,xn should not be changed. (So it
would be okay for the fold-like function to decide to compute (((x1 `f` x2)
`f` x3) `f` ... xn), it would also be okay for the fold-like function to
decide to compute (((x1 `f` x2) `f` (x3 `f` x4)) `f` ... xn), but it would
not be okay for the fold-like function to decide to compute ((((x2 `f` x3)
`f` x1) `f` x4) `f` ... xn).)

That is a property of the fold-like function, not a property of f. Also, it
is not making an assumption about f being associative. It is just saying
what the fold-like function should be allowed to do, and not allowed to do,
given an arbitrary f.


2015-10-28 20:05 GMT+01:00 Marcin Mrotek <marcin.jan.mrotek at gmail.com>:

> And look at what we have: A definitive answer to OP's question:
>>
>> Question: What is a fold of type "(a -> a -> a) -> [a] -> a" that
>> promises to call its first parameter "associatively"?
>>
>> Answer: It is a fold equivalent to a fold1 (left or right, it doesn't
>> matter).
>>
>> That's nice.
>>
>> But is that all we can come up with? Does it really do justice to the
>> original question? Viz.
>>
>
> Hello,
>
> Sorry for jumping into the thread, but I've read the previous responses,
> and I still don't get it (perhaps it's because I'm not a native English
> speaker): what does "associatively" mean in this context? From what I
> understand, "associativity" is a property of a function, that f (f a b) c =
> f a (f b c). Nothing more, nothing less. In order to encode this property
> in the type of a "fold" function, you'd need dependent types and a
> type-level proof that a given function is associative. Without dependent
> types, you can only trust the user to either supply an associative
> function, or accept wrong results (like REPA does). Am I missing something?
>
> Best regards,
> Marcin Mrotek
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151028/1f97e0dd/attachment.html>