How to fix palindrome function in Haskell

Question

I'm trying to figure out why my palindrome function isn't working. Does it have to do with how I'm declaring 'w'? I'm attempting to take out all the letters and digits in a string, convert them to uppercase, and places it in a new string 'w'. I attempt to see if they're the same by checking if 'w' is the same as it is reverse

isPalindrome :: [Char] -> Bool
isPalindrome [] = True
isPalindrome [a] = True
isPalindrome (x:xs) | w == reverse w = True
                    | otherwise = False
                         where w        | isDigit x = x:(isPalindrome xs)  -- figured isDigit and isAlpha would be okay to use
                                        | isAlpha (toUpper x) = x:(isPalindrome xs)  -- put this under so digits wouldn't have to do toUpper
                                        | otherwise = isPalindrome xs

Obviously I expect the result to return true if it's a palindrome and false otherwise.

The error I'm getting currently is:

    * Couldn't match expected type `[Char]' with actual type `Bool'
    * In the expression: isPalindrome xs
      In an equation for `w':
          w | isDigit x = x : (isPalindrome xs)
            | isAlpha (toUpper x) = x : (isPalindrome xs)
            | otherwise = isPalindrome xs
      In an equation for `isPalindrome':
          isPalindrome (x : xs)
            | w == reverse w = True
            | otherwise = False
            where
                w | isDigit x = x : (isPalindrome xs)
                  | isAlpha (toUpper x) = x : (isPalindrome xs)
                  | otherwise = isPalindrome xs
   |
48 |                                         | otherwise = isPalindrome xs
   |

x:(isPalindrome xs) Please explain to your nearest rubber duck what this thing means, in detail. — n. 1.8e9-where's-my-share m.
w is supposed to be the same type as the string I'm taking in. So it should be [Char] — Sean Roberts
| otherwise = isPalindrome xs says it's a Bool (because that's what isPalindrome returns). — melpomene

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2019-09-11T19:08:06

You try to do too much in a single function. Your w is supposed to be a string. But you define w as:

where w | isDigit x = x:(isPalindrome xs)
        | isAlpha (toUpper x) = x:(isPalindrome xs)
        | otherwise = isPalindrome xs

You here thus write a condition, which is fine, but then you construct a list that starts with x (in the first two cases), and has isPalindrome xs as tail. But isPalindrome xs is not a String, it should be, given the function signature, be a Bool.

That being said, I think you make things too complicated. We can make a String where we filter out the characters that are not digits or alpha characters with:

filter (\x -> isDigit x || isAlpha x)

or as @melpomene says, we can use isAlphaNum :: Char -> Bool:

filter isAlphaNum

So we can write such function as:

import Data.Char(isAlphaNum)

isPalindrome :: String -> Bool
isPalindrome s = w == reverse w
    where w = filter isAlphaNum s

We can use applicative style here, and work with:

import Control.Applicative(ap)
import Data.Char(isAlphaNum)

isPalindrome :: String -> Bool
isPalindrome = ((==) <*> reverse) . filter isAlphaNum

We do not need to write cases for the empty list, or a singleton list, since these will be covered by the w == reverse w: the reverse of an empty list and singleton list is an empty and singleton list respectively.

You can implement filtering yourself, but I suggest you do that in a separate function, not trying to do this in the same function. In fact it might make sense to separate the preprocessing step (removing characters that are non-digits and non-alphas from the string) in a separate function.

How to fix palindrome function in Haskell

1 Answers