CODEWITHSUNDEEP
haskellmonads
Neil Mitchell
Neil Mitchell

Reputation: 9250

Why is Haskell monadic bind left-associative?

The >>= and >> operators are both infixl 1. Why the left-associativity?

In particular, I observe the equivalences:

(do a; b; c ) == (a >> (b >> c))   -- Do desugaring
(a >> b >> c) == ((a >> b) >> c)   -- Fixity definition

So do is desugared differently to how the fixity definition naturally works, which is surprising.

Upvotes: 16

Views: 1344

Answers (2)

leftaroundabout
leftaroundabout

Reputation: 120711

>>= must surely be left-associative.

Prelude> ["bla","bli di","blub"] >>= words >>= reverse
"albilbidbulb"
Prelude> ["bla","bli di","blub"] >>= (words >>= reverse)

<interactive>:3:30: error:
    • Couldn't match expected type ‘[[b0]]’
                  with actual type ‘String -> [String]’
    • Probable cause: ‘words’ is applied to too few arguments
      In the first argument of ‘(>>=)’, namely ‘words’
      In the second argument of ‘(>>=)’, namely ‘(words >>= reverse)’
      In the expression:
        ["bla", "bli di", "blub"] >>= (words >>= reverse)

And >> pretty much follows >>=; if it had another fixity it would not only feel weird as Lennart said, it would also prevent you from using both operators in a chain:

Prelude> ["bla","bli di","blub"] >>= words >> "Ha"
"HaHaHaHa"
Prelude> infixr 1 ⬿≫; (⬿≫) = (>>)
Prelude> ["bla","bli di","blub"] >>= words ⬿≫ "Ha"

<interactive>:6:1: error:
    Precedence parsing error
        cannot mix ‘>>=’ [infixl 1] and ‘⬿≫’ [infixr 1] in the same infix expression

Upvotes: 16

AJF
AJF

Reputation: 11923

>>= is left-associative because it's convenient. We want m >>= f1 >>= f2 to be parsed as (m >>= f1) >>= f2, not as m >>= (f1 >>= f2), which would likely not type check, as pointed out in the comments.

The associativity of >> however, is simply a mirror of >>=. This is likely for the sake of consistency, since we can prove that >> is associative via the third monad law: (m >>= f) >>= g ≡ m >>= ( \x -> f x >>= g ). That is to say, its associativity doesn't theoretically matter. Here is the proof:

-- Definition:
a >> b ≡ a >>= (\_ -> b)

-- Proof: (a >> b) >> c ≡ a >> (b >> c)
  (a >> b) >> c
≡ (a >>= (\_ -> b)) >> c                  -- [Definition]
≡ (a >>= (\_ -> b)) >>= (\_ -> c)         -- [Definition]
≡ a >>= (\x -> (\_ -> b) x >>= (\_ -> c)) -- [Monad law]
≡ a >>= (\_ -> b >>= (\_ -> c))           -- [Beta-reduction]
≡ a >>= (\_ -> b >> c)                    -- [Definition]
≡ a >> (b >> c)                           -- [Definition]
∎

do-notation de-sugars differently because it has a different goal. Essentially, since do-notation is essentially writing out a lambda, right-association is needed. This is because m >>= (\v -> (...)) is written as do {v <- m; (...)}. As earlier, the de-sugaring of >> here seems to follow >>= for the sake of consistency.

Upvotes: 9

Related Questions