unbound variables in monad associativity law

Question

Using ghci I have computed:

Prelude> let m = [1,2]
Prelude> let ys = [4, 5, 6]
Prelude> m >>= (\x -> ys >>= (\y -> return (x, y)))
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6)]

The monadic expression above doesn't seem to correspond to either side of the monad associativity law:

(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

I would like to know how monad associativity can be applied to the expression:

m >>= (\x -> ys >>= (\y -> return (x, y))) 

Because return (x,y) closes on both the surrounding function and the one containing it, it seems that an intermediate monad, as exists on the left side of the associativity law (m >>= f), cannot exist in this example.

Answer 1

Indeed, it's not possible to directly apply the associative law, because of the scope of x in the original expression:

import Control.Monad (liftM)

test = let m = [1,2]
           ys = [4, 5, 6]
       in m >>= (\x -> ys >>= (\y -> return (x, y)))

However, we can reduce the scope of x if we include it into the result of the first monadic computation. Instead of returning [Int] in x -> ys, we'll use \x -> liftM ((,) x) ys and return [(Int,Int)], where the first number in each pair is always x and the second is one of ys. (Note that for lists liftM is the same as map.) And the second function will read the value of x from its input:

test1 = let m = [1,2]
            ys = [4, 5, 6]
        in m >>= (\x -> liftM ((,) x) ys >>= (\(x', y) -> return (x', y)))

(The monadic function \(x', y) -> return (x', y) could be now simplified just to return, and subsequently >>= return removed completely, but let's keep it there for the sake of the argument.)

Now each monadic function is self-contained and we can apply the associativity law:

test2 = let m = [1,2]
            ys = [4, 5, 6]
        in (m >>= \x -> liftM ((,) x) ys) >>= (\(x, y) -> return (x, y))

Answer 2

I think that you're confusing the monadic laws for the structure of a monadic expression. The monadic associativity law states that the expression (m >>= f) >>= g must be equivalent to the expression m >>= (\x -> f x >>= g) for the data type of m to be considered a monad.

This does not imply that every monadic expression must be of the form (m >>= f) >>= g.

For example m >>= f is a perfectly valid monadic expression even though it's not of the form (m >>= f) >>= g. However it still obeys the monadic associativity law because m can be expanded to m >>= return (from the monadic right identity law m >>= return ≡ m). Hence:

m >>= f

-- is equivalent to

(m >>= return) >>= f

-- is of the form

(m >>= f) >>= g

In your example m >>= (\x -> ys >>= (\y -> return (x, y))) is of the form m >>= f where f is \x -> ys >>= (\y -> return (x, y)).

Although \x -> ys >>= (\y -> return (x, y)) is not of the form \x -> f x >>= g (from the right hand side of the monadic associativity law) it doesn't mean that it breaks the monadic laws.

The expression m >>= (\x -> ys >>= (\y -> return (x, y))) can be expanded into the monadic associative form by substituting m >>= return for m:

(m >>= return) >>= (\x -> ys >>= (\y -> return (x, y)))

-- is of the form

(m >>= f) >>= g

-- and can be written as

m >>= (\x -> return x >> (\x -> ys >>= (\y -> return (x, y))))

Hope that clarifies things.

Answer 3

The monadic law applies to functions of one arguments only. The expression

xs >>= (\x -> ys >>= (\y -> (x, y)))

is really equivalent to:

xs >>= \x -> fmap ($ x) $ ys >>= \y -> return (\x -> (x,y))

(if we were to avoid capturing x)

So you can't apply the same laws - we have fmap as f and no g from the associativity law.

The above is of course the same as:

xs >>= \x -> fmap ($ x) $ fmap (\y x -> (x,y)) ys

or

xs >>= \x -> fmap (\y -> (x,y)) ys