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

Question

I need to check Haskell if a four-digit number is a palindrome, the problem is that I cannot use lists, and despite having a fixed digit number, I have to use recursion. I was thinking about a problem, and I could not get a solution using recursion. The closest I could get was the following:

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 ideas? thanks

Answer 1

How easy is it to check if a number matches its appeal?

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

This allows negative numbers, such as -121 , to be palindromes that are easy to check if you don't want this to be true.

 nonNegativePalindrome x = x >= 0 && palindrome x 

reversal gives an integer with numbers in the reverse order of our input (ignoring infinite leading zeros implicit in 12 == ...000012 ).

reversal works by quotRem numbers below (using quotRem , which is very similar to divMod ) and stacking them in the reverse order (by multiplying and adding).

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

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

A more detailed explanation of how to achieve this solution in this blog post .

Answer 2

Well, this is really a little more complicated and more mathematically than Haskell, so let's look at a possible solution (assuming a decimal system).

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

 (q,r) = n `divMod` m 

to get the numbers q and r , so that q * m + r = n with 0 <= r < q . For m = 10 it will be convenient to obtain (for positive n ):

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

note : I have had this wrong for some time - I hope this is right now - the extreme cases are really complicated.

 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) 

Obviously, 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 edges include the following:

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

• Obvious negative numbers should not be palindromes
• if all digits are 0, then this is a palindrome
• single-digit numbers are palindromes, if we really only look at length 1 (this was bad for me, since inner a type like 1011 is one nubmer number 1 )

The rest are based on these observations:

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

To be safe, you can check it with Quickcheck:

Let me use Quickcheck to test it (should be a good 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 || pn == (reverse (show n) == show n)) where more = stdArgs { maxSuccess = 10000, maxSize = 999999 } 

It looks fine:

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

Answer 3

If only four digits are taken into account, you can recursively subtract 1001 to check if the first and last digits are equal, and then subtract 0110 to check if the middle digits are equal.

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

Note that this function will give incorrect results for numbers outside the range [1000,9999].

Answer 4

Too bad you can't use lists. Here is a 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