Home > Mobile >  Haskell monad for isPalindrome
Haskell monad for isPalindrome

Time:11-14

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.

CodePudding user response:

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".

  • Related