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

Question

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

Answer 1

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.

Answer 2

Ok, this is indeed a bit tricky and more math than Haskell so let's look at a possible solution (assuming a decimal system).

The idea is to use div and mod to get at the highest and lowest digit of a number. Remember that you can write

(q,r) = n `divMod` m

to get numbers q and r so that q * m + r = n with 0 <= r < q. For m = 10 this will conveniently get (for positive n):

• in q all but the last digits
• in r the last digit

remark: I had this wrong for some time - I hope it's correct now - the edge cases are really tricky.

palindrome :: Integer -> Bool
palindrome n = palin n (digits n)
  where
    palin x dgts
      | x < 0     = False
      | x == 0    = True
      | x < 10    = dgts == 1
      | otherwise = q == x `mod` 10 && palin inner (dgts-2)
      where
        inner = r `div` 10
        (q,r) = x `divMod` size
        size  = 10^(dgts-1)

digits :: Integer -> Integer
digits x
  | x < 10    = 1
  | otherwise = 1 + digits (x `div` 10)

Obvious I did not know the size of your problem so digits will look for the number of digits:

• digits 5445 = 4
• digits 123 = 3
• ...

The edge cases are these:

  | x < 0     = False
  | x == 0    = True
  | x < 10    = digits == 1

• Obvious negative numbers should not be palindromes
• if all digits are 0 then it's an palindrome
• one-digit numbers are palindromes if indeed we are looking only at length 1 (this had me bad, as the inner of stuff like 1011 is a one digit nubmer 1)

The rest is based on this observations:

• x div 10^(digits-1) = the highest digit (5445 div 1000 = 5)
• x mod 10^(digits-1) = all but the highest digit (5445 mod 1000 = 445)
• x mod 10 = the lowest digit (5445 mod 10 = 5)
• number div 10 = remove the lowest digit (5445 div 10 = 544)

just to be safe let's test it using Quickcheck:

Let's use Quickcheck to test it (should be a nice example :D )

module Palindrome where

import Test.QuickCheck

main :: IO ()
main = do
  checkIt palindrome

palindrome :: Integer -> Bool
palindrome n = palin n (digits n)
  where
    palin x dgts
      | x < 0     = False
      | x == 0    = True
      | x < 10    = dgts == 1
      | otherwise = q == x `mod` 10 && palin inner (dgts-2)
      where
        inner = r `div` 10
        (q,r) = x `divMod` size
        size  = 10^(dgts-1)

digits :: Integer -> Integer
digits x
  | x < 10    = 1
  | otherwise = 1 + digits (x `div` 10)

checkIt :: (Integer -> Bool) -> IO ()
checkIt p =
  quickCheckWith more (\n -> n < 0 || p n == (reverse (show n) == show n))
  where more = stdArgs { maxSuccess = 10000, maxSize = 999999 }

seems ok:

runghc Palindrom.hs 
+++ OK, passed 10000 tests.

Answer 3

If only four digit numbers considered, you can recursively subtract 1001 to check if first and last digits are equal and then subtract 0110 to check if middle digits are equal.

pldrm :: Int -> Bool
pldrm x
  | x > 1000 = pldrm (x - 1001)
  | x > 100  = pldrm (x - 110)
  | otherwise = x == 0

Please note that this function will give incorrect results for numbers outside of [1000,9999] range.

Answer 4

It is a pity that you cannot use lists. Here is cumbersome solution based on arithmetic operations (works only for four-digit numbers):

pldrm :: Int -> Bool -- no need for Integer if you work only with four
                     -- digit numbers
pldrm x = (div x 1000 == mod x 10) && (div y 10 == mod y 10)
    where y = rem x 1000 `quot` 10 -- extracts two inner digits

> pldrm 3113
True
> pldrm 3111
False