8

The 6th of the 99 Haskell questions on wiki.haskell.org presents a monadic way to test whether a list (something of type [a]) is a palindrome:

isPalindromeM :: (Eq a) => [a] -> Bool isPalindromeM = reverse >>= (==)

(here reverse :: [c] -> [c] takes a list and outputs a list in backwards order).

The bind operation implies a monad is at play here, but what is this monad?

Since isPalindrome involves lists, my first guess is that the monad is related to the List one, but I don't see how to draw the connection.

Improve this question
2
  • 2
    Functions have an applicative/monad instance. But I see no reason to use the monad instance over the applicative (other than dropping a flip). So I'd ask the author, why not isPalindromA = (==) <*> reverse? Commented Nov 12, 2021 at 8:38
  • @Micha I totally agree, especially since I find the applicative form more transparent. My question was aimed more toward “why does this monadic expression work?” Commented Nov 12, 2021 at 16:16

1 Answer 1

Reset to default
10

It took me some time to find the monad, and since it is not related to List, I figured I'd post an answer.

The expression reverse >>= (==) implies the type of reverse is m a, for some monad m, hence m a is the type [c] -> [c]. We also need isPalindromeM to have type [c] -> Bool, and the bind expression implies m b is identical to [c] -> Bool. Finally this context requires (==) :: [c] -> [c] -> Bool to have the type a -> m b.

Therefore we deduce a is [c] and b is Bool, and the monad m takes a type a and sends it to the function type [c] -> a. This suggests the monad at play is Monad ((->) [c]). defined here

If there's some moral to the story, perhaps it's "you can make a monad out of anything".

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Basically right, but I'd make the small nit that the monad instance is technically ((->) [c]), i.e. it has been specialized to r ~ [c]. ((->) r) is a monad for any r, and in your case r is [c].
One way to check whether a piece of code uses the list monad is to check what is "send" into (>>=). In your case reverse >>= .... Since reverse is not a list, this is not the list monad.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.