CODEWITHSUNDEEP
haskellrecursionpalindrome
s0rry
s0rry

Reputation: 3

Haskell Recursion Function (guards required)

Can someone tell me what's wrong with my implementation of this Haskell palindrome checker? Note: Before calling this on the the input string, the string is "cleaned" to get rid of case discrepancies and any non-alphabet characters.

checkPalindromeClean :: [Char] -> Bool
checkPalindromeClean inpString
    | length inpString == 0 = True
    | length inpString == 1 = True
    | head inpString == last inpString = checkPalindromeClean (init (tail inpString))
    otherwise False

Here is the (cryptic) error message I am receiving:

jdoodle.hs:43:42: error:
    • Couldn't match expected type ‘Bool -> Bool -> Bool’
                  with actual type ‘Bool’
    • The function ‘checkPalindromeClean’
      is applied to three value arguments,
        but its type ‘[Char] -> Bool’ has only one
      In the expression:
        checkPalindromeClean (init (tail inpString)) otherwise False
      In an equation for ‘checkPalindromeClean’:
          checkPalindromeClean inpString
            | length inpString == 0 = True
            | length inpString == 1 = True
            | head inpString == last inpString
            = checkPalindromeClean (init (tail inpString)) otherwise False
   |
43 |     | head inpString == last inpString = checkPalindromeClean (init (tail inpString))
   |                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

Upvotes: 0

Views: 163

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476803

otherwise is a condition too (it is an alias of True), and therefore should be used as a guard as well, so:

checkPalindromeClean :: [Char] -> Bool
checkPalindromeClean inpString
    | length inpString == 0 = True
    | length inpString == 1 = True
    | head inpString == last inpString = checkPalindromeClean (init (tail inpString))
    | otherwise = False

Using length :: [a] -> Int, init :: [a] -> [a] and last :: [a] -> a all run in 𝓞(n), therefore the algorithm will run in 𝓞(n2), which is not very efficient.

Upvotes: 4

Related Questions