I said "associatively" to be a place holder for a property I was trying to express, but unable to formalize. So yes, from what I understand associativity is a property of a function and has a formalization.

As for the category theory, this is where I thought that this calling hierarchy might already be formalized in. I thought it would be nice to say something to the effect of "This fold has x property and exploits it to support parallelization". Obviously f does not need to be associative if the caller of the fold understands that only the x property is promised in the implementation.

On Wed, Oct 28, 2015 at 3:05 PM, Marcin Mrotek <marcin.jan.mrotek@gmail.com> wrote:

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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe