Search code examples
listhaskellpalindromedeclarative

Decide(in Haskell) if a number is or not a palindrome without using lists

I need to check in Haskell if a four digit number is a palindrome, the problem is that I can't use lists, and in spite of having a fixed digit number, I should use recursion. I have been think on the problem and I couldn't get a solution using recursion. The closest that I could get was this: 

pldrm :: Integer -> Bool
pldrm x
    |x > 9999 = False
    |x > 999 = (div x 1000 == mod x 10) && (mod (div x 100) 10) == div (mod x 100) 10
    |otherwise = False

Do you have any idea? thanks

Solution

  • How about just checking if a number is equal to its reversal?

    palindrome :: Integer -> Bool
palindrome x = reversal x == x

reversal :: Integral a => a -> a
reversal = go 0
  where go a 0 = a
        go a b = let (q,r) = b `quotRem` 10 in go (a*10 + r) q

    This lets negative numbers like -121 be palindromes, which is easy to check for if you don't want that to be true.

    nonNegativePalindrome x = x >= 0 && palindrome x

    reversal gives us the integer with digits in reverse order of our input (ignoring the infinite leading zeroes implicit in 12 == ...000012).

    reversal works by peeling off the digits from the bottom (using quotRem, which is a lot like divMod) and putting them together in reverse order (via muliplication and adding).

    reversal 12345
= go 0 12345 
= go 5  1234
= go 54  123
= go 543  12
= go 5432  1
= go 54321 0
= 54321

    It's worth noting that n == reversal $ reversal n only if n is zero or has a non-zero 1s digit. (reversal (reversal 1200) == 12), but that integers in the range of reversal are all invertible: reversal x == reversal (reversal (reversal x)) forall x.

    More thorough explanation of how to reach this solution in this blog post.