Решите (в Haskell), является ли число палиндромом, не используя списки

Как насчет того, чтобы просто проверить, равно ли число его обращению?

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

Это позволяет отрицательным числам, таким как -121, быть палиндромами, что легко проверить, если вы не хотите, чтобы это было правдой.

nonNegativePalindrome x = x >= 0 && palindrome x

reversal дает нам целое число с цифрами в порядке, обратном нашему вводу (игнорируя бесконечные начальные нули, неявные в 12 == ...000012).

reversal работает, отделяя цифры снизу (используя quotRem, что очень похоже на divMod) и сложить их вместе в обратном порядке (посредством умножения и сложения).

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

Стоит отметить, что n == reversal $ reversal n только в том случае, если n равно нулю или имеет ненулевую цифру 1. (reversal (reversal 1200) == 12), но все целые числа в диапазоне reversal обратимы: reversal x == reversal (reversal (reversal x)) для всех x.

Более подробное объяснение того, как найти это решение, в этом сообщении блога.

Хорошо, это действительно немного сложно и больше математики, чем Haskell, поэтому давайте посмотрим на возможное решение (предполагая десятичную систему).

Идея состоит в том, чтобы использовать div и mod для получения старшей и младшей цифры числа. Помните, что вы можете написать

(q,r) = n `divMod` m

получить числа q и r так, чтобы q * m + r = n с 0 <= r < q. Для m = 10 это будет удобно (для положительного n):

• в q все, кроме последних цифр
• в r последняя цифра

примечание: какое-то время я ошибался в этом - надеюсь, теперь это правильно - пограничные случаи действительно сложны.

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)

Очевидно, я не знал размера вашей проблемы, поэтому digits будет искать количество цифр:

• цифры 5445 = 4
• цифры 123 = 3
• ...

Пограничные случаи таковы:

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

• Очевидные отрицательные числа не должны быть палиндромами
• если все цифры 0 то это палиндром
• однозначные числа являются палиндромами, если мы действительно смотрим только на длину 1 (это меня расстроило, так как inner таких вещей, как 1011, является однозначным числом 1)

Остальное основано на этих наблюдениях:

• x div 10^(digits-1) = старшая цифра (5445 div 1000 = 5)
• x mod 10^(digits-1) = все, кроме старшей цифры (5445 mod 1000 = 445)
• x mod 10 = самая младшая цифра (5445 mod 10 = 5)
• number div 10 = удалить младшую цифру (5445 div 10 = 544)

просто на всякий случай давайте проверим это с помощью Quickcheck:

Давайте используем Quickcheck, чтобы проверить это (должен быть хороший пример: 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 }

вроде нормально:

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

Если рассматриваются только четырехзначные числа, вы можете рекурсивно вычесть 1001, чтобы проверить, равны ли первая и последняя цифры, а затем вычесть 0110, чтобы проверить, равны ли средние цифры.

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

Обратите внимание, что эта функция будет давать неверные результаты для чисел вне диапазона [1000,9999].

Жаль, что нельзя использовать списки. Вот громоздкое решение, основанное на арифметических операциях (работает только для четырехзначных чисел):

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