Question

Are the following two implementations of flatten equivalent for all well-behaved Monads?

flatten1 xss = do
    xs <- xss
    x <- xs
    return x

flatten2 xss = do
    xs <- xss
    xs
Was it helpful?

Solution

Yes, they're identical. They're desugared as

flatten1 xss =
    xss >>= \xs -> xs >>= \x -> return x

flatten2 xss = do
    xss >>= \xs -> xs

The first one is equivalent to

xss >>= \xs -> xs >>= return

and by the Right identity monad law equivalent to

xss >>= \xs -> xs

OTHER TIPS

In short, yes. To prove it:

You've written:

xss >>= (\xs -> xs >>= \x -> return x)
xss >>= (\xs -> xs >>= return) -- eta

in the first and

xss >>= (\xs -> xs)
xss >>= id

according to the monad laws, return is a right identity so that

m >>= return === m

so we can do

xss >>= (\ xs -> xs >>= return )
xss >>= (\ xs -> xs )
xss >>= id
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top