Search code examples
stringlisthaskellpalindrome

Match type error when counting palindromes in a list in Haskell


I'm getting a match type [Char] with String -> Bool error:

isPalindrome :: String -> Bool
isPalindrome w = w == reverse w

countPalindromes :: [String] -> Int
countPalindromes ss = length (filter (== isPalindrome) ss)

countPalindromes uses isPalindrome to check if a string is a palindrome.

I now have a different issue than in my first question about this palindrome count task. The first issue was solved, and I was instructed to open a new question to solve the new issue. Which is why this is a different question.


Solution

  • isPalindrome :: String -> Bool, which is to say that it expects a string, then gives you a boolean to say whether or not that string is a palindrome.

    (==) :: Eq a => a -> a -> Bool, which is to say that it expects two values of typeclass Eq (in other words: anything equatable) and tells you whether or not they are equal.

    Pair those together and you get (== isPalindrome) :: (String -> Bool) -> Bool*. You've handed (==) a String -> Bool value, so it's expecting one more and will tell you if the two are equal. That's not quite what you want, though. You're not comparing two functions....

    In fact, you're not comparing any two things at all. You only want to see which values passed to countPalindromes return True when called by isPalindrome. That's what filter is for!

    filter :: (a -> Bool) -> [a] -> [a]
    

    It's looking for an a -> Bool to pass as the first argument. This is the function that will be deciding what makes it through the filter and what doesn't, and in this case you want to use some derivation of isPalindrome. Looking again at isPalindrome in this context we see:

    isPalindrome :: String -> Bool
    

    that looks an awful lot like an a -> Bool function! Let's try substituting all the as in filter's type signature with String.

    filter :: (String -> Bool) -> [String] -> [String]
    

    That looks like it's exactly what you're wanting! Try, then, using filter isPalindrome instead of filter (== isPalindrome).


    * nitpick: functions (more generally: values of type (-> r)) are not members of the Eq typeclass so you'd actually get an error saying that you can't tell if a String -> Bool is equal to another String -> Bool. It's not relevant to the problem at-hand, though, so I'm pretending that's not an issue and burying this explanation down here.