How do operator associativity, the associative law and value dependencies of monads fit together?

Question

On the one hand the monadic bind operator >>= is left associative (AFAIK). On the other hand the monad law demands associativity, i.e. evaluation order doesn't matter (like with monoids). Besides, monads encode a value dependency by making the next effect depend on the result of the previous one, i.e. monads effectively determine an evaluation order. This sounds contradictory to me, which clearly implies that my mental representation of the involved concepts is wrong. How does it all fit together?

Pietje

No time for a full answer (and I doubt I could give a better one than many others), but in brief the "associative law" for monads isn't associativity of the >>= operator itself - if you check the standard statement of the law you will see it's somewhat more involved. It's equivalent in fact to the associativity (in the normal sense) of the Kleisli composition operator. – Ansela

It sounds contradictory. Can you come up with a concrete example of why you think it is contradictory? – Elgon

"evaluation order doesn't matter" that's commutativity, not associativity. monads' associativity just means that it's OK for the do notation to be multi-line (it doesn't have to be binary, like >>=), to be re-grouped at will as long as the lines' order stays the same (so the inner brackets can be omitted). Just like the function composition's associativity means we can write composition chains non-parenthesized too. – Feathering

@WillNess My understanding of the associative property is that it allows a composition of more than two semigroups, for instance, to be computed in parallel, because the order in which op1 <> op2 operations are evaluated doesn't matter. I don't mean the order of operands but the operand1 operator operand2 operations as a whole. However, this doesn't work for >>= anyway, because of the underlying type. – Pietje

ah, now it's clear. so, with monads, as was already said here, what's associative is >=>. and its combinations too could be calculated in parallel, out of order! but, what it calculates is the combined action that is yet to be run. see? when the combined action runs, it'll run its constituent actions left-to-right, strictly in order. because that's how the underlying >>= is defined. (you really should've included that example of your understanding in the question from the start!) – Feathering

@WillNess Ya, sorry, higher order confusion.. – Pietje

Answer 1

On the one hand the monadic bind operator >>= is left associative

Yes.

Prelude> :i >>=
class Applicative m => Monad (m :: * -> *) where
  (>>=) :: m a -> (a -> m b) -> m b
  ...
    -- Defined in ‘GHC.Base’
infixl 1 >>=

That's just the way it's defined. + is left-associative too, although the (addition-) group laws demand associativity.

Prelude> :i +
class Num a where
  (+) :: a -> a -> a
  ...
    -- Defined in ‘GHC.Num’
infixl 6 +

All an infixl declaration means is that the compiler will parse a+b+c as (a+b)+c; whether or not that happens to be equal to a+(b+c) is another matter.

the monad law demands associativity

Well, >>= is actually not associative. The associative operator is >=>. For >>=, already the type shows that it can't be associative, because the second argument should be a function, the first not.

Besides, monads encode a value dependency by making the next effect depend on the result of the previous one

Yes, but this doesn't contradict associativity of >=>. Example:

teeAndInc :: String -> Int -> IO Int
teeAndInc name val = do
   putStrLn $ name ++ "=" ++ show val
   return $ val + 1

Prelude Control.Monad> ((teeAndInc "a" >=> teeAndInc "b") >=> teeAndInc "c") 37
a=37
b=38
c=39
40
Prelude Control.Monad> (teeAndInc "a" >=> (teeAndInc "b" >=> teeAndInc "c")) 37
a=37
b=38
c=39
40

Flipping around the parens does not change the order / dependency between the actions (that would be a commutativity law, not an associativity one), it just changes the grouping of the actions.

Ackerley

OK, I think I do understand it a bit better. Function composition in math is associative whereas application is left associative. By using kleisli composition we can defer the application and thus remain associative. – Pietje

Y...yeah. But FTR, associativity of Kleisli composition does not automatically follow from the fact that Kleislis are functions. – Ackerley

@scriptum: I think you’re just mixing up two concepts of “associativity” here: operator associativity and the associative property. “>>= is left-associative” just means a >>= b >>= c is parsed as (a >>= b) >>= c, which is just for convenience, to avoid having to write some parentheses. We could declare it infix 1 >>= instead. Whereas “>=> is associative” means that (a >=> b) >=> c is equal to a >=> (b >=> c), a much stronger statement about the actual semantics. – Chemoprophylaxis