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

Womenfolk

Compute first and last digit, check them for equality, remove them, and recurse. Should be doable with artihmetic & logical operations, only. – Lesser

This is like telling a Lisp programmer not to use lists. I don't think that there is anything worth learning in it. – Burkett

@Vektorweg ... oh there is ... ;) – Ignaz

Vektorweg: just use another Monoid! – Chantalchantalle

@CarstenKönig @Chantalchantalle There could be a Traversable instance of the number, i guess. Then just compare the backward traversed number with the regular traversed number. – Burkett

@Vektorweg my guess: if Ivan is not allowed to do it using list than maybe this approach would be over the top too ;) - but you can add it to the answers for future references - I will gladly upvote – Ignaz

Vektorweg: Yeah, I've been looking at mono-traversable for that reason. – Chantalchantalle

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.

Chantalchantalle

+1 - really nice answer! I think you should explain it a bit more (I think the algorithm is not that easy to see) and then the OP should switch the accepted answer to this! – Ignaz

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.

Ignaz

thank you, this is the perfect solution for the problem – Cheloid

Can't the definition of inner be simplified to inner = (x `mod` size) `div` 10? – Galilean

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.

Haim

This function is correct only for numbers >= 1000 and =< 9999, i.e. "four digit numbers". According to OP's problem statement it seems that this is exactly what he asks for. – Haim

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

Merci

@WillNess, indeed! I've improved this mess a little bit :-) – Merci

great; just one more thing, :) f x | b = True | otherwise = False is more idiomatically written f x = b. – Unciform

@WillNess, oh yeah! Although I have to remove the first guard too in this case. Anyway, it looks like a decent solution now! Thanks! – Merci

not necessarily, no. you could have f x | t = error | otherwise = b. :) and you're welcome. – Unciform

Answer 5

isPolindrom :: Integer -> Bool 
isPolindrom n = if let i = read (reverse (show n)) :: Integer in i==n then True else False

Freeland

Hi @Seliverstov. Thank you for your answer. Although the code it's fine and simple, it's a good practice adding some explanation about it – Cheloid

if a then True else False is the same as a. show produces a list, and reverse reverses a list, which seems to contradict the requirement in the question. – Unciform