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