Behavior of reverse >>= (==)

Question

A function for determine if a string is a palindrome can be implemented in a pointfree applicative manner via

pal1 = (==) <$> reverse <*> id 

And here is a monadic version

reverse >>= (==)

How does the modadic version work with no explicit call to id? I attempted to view the poinful representation using pointful and get back the same function.

Answer 1

This works using the fact that x -> y can be regarded as a kind of "reader monad". If we were to say

type Reader r x = r -> x

then we have an instance of Monad (Reader r). So we can see that

reverse :: [x] -> [x]

is actually

reverse :: Reader [x] [x]

Similarly,

(==) :: [x] -> [x] -> Bool

can be written as

(==) :: [x] -> Reader [x] Bool

Then (>>=) joins the two together.

So... We start with reverse, which is a Reader action that reads a list and returns a list. We then use >>= to pass that to ==, which is a function that takes a list, and returns a Reader [x] Bool.

In short, the input list is duplicated by the action of Reader, which basically takes an input and passes it to every function in the chain. (That's what the reader monad is.)

I hope that made some kind of sense... It took me a while to figure out!

Answer 2

Let's have a look at the Monad instance for ((->) r):

instance Monad ((->) r) where
    return = const
    f >>= k = \ r -> k (f r) r

and then simply fill in your monadic code:

reverse >>= (==) = \r -> (==) (reverse r) r

which we can write in a more familiar way:

\r -> reverse r == r