Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

returning an element extracted from a monad; redundant?

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
like image 391
fredoverflow Avatar asked Jun 20 '13 15:06

fredoverflow


2 Answers

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
like image 64
Petr Avatar answered Sep 18 '22 23:09

Petr


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
like image 39
Daniel Gratzer Avatar answered Sep 19 '22 23:09

Daniel Gratzer