Decidir (en Haskell) si un número es o no un palíndromo sin usar listas

Te damos la bienvenida a nuestra página, en este lugar vas a encontrar la solucíon a lo que estabas buscando.

¿Qué tal simplemente verificar si un número es igual a su inversión?

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

Esto permite números negativos como -121 ser palíndromos, que es fácil de comprobar si no quieres que sea true.

nonNegativePalindrome x = x >= 0 && palindrome x

reversal nos da el número entero con dígitos en orden inverso de nuestra entrada (ignorando los ceros iniciales infinitos implícitos en 12 == ...000012).

reversal funciona despegando los dígitos de la parte inferior (usando quotRem, que se parece mucho a divMod) y juntarlos en orden inverso (mediante la multiplicación y la adición).

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

Vale la pena señalar que n == reversal $ reversal n sólo si n es cero o tiene un dígito de unos distintos de cero. (reversal (reversal 1200) == 12), pero que enteros en el rango de reversal son todos invertibles: reversal x == reversal (reversal (reversal x)) para todos x.

Una explicación más detallada de cómo llegar a esta solución en esta publicación de blog.

De acuerdo, esto es un poco complicado y más matemático que Haskell, así que veamos una posible solución (asumiendo un sistema decimal).

La idea es usar div y mod para obtener el dígito más alto y más bajo de un número. Recuerda que puedes escribir

(q,r) = n `divMod` m

para obtener números q y r de modo que q * m + r = n con 0 <= r < q. Para m = 10 esto obtendrá convenientemente (para positivo n):

• en q todos menos los últimos dígitos
• en r el último dígito

observación: Tuve esto mal durante algún tiempo, espero que sea correcto ahora, los casos extremos son realmente complicados.

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)

Obviamente, no sabía el tamaño de tu problema, así que digits buscará el número de dígitos:

• dígitos 5445 = 4
• dígitos 123 = 3
• ...

Los casos extremos son estos:

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

• Los números negativos obvios no deben ser palíndromos
• si todos los dígitos son 0, entonces es un palíndromo
• Los números de un dígito son palíndromos si de hecho estamos mirando solo en la longitud 1 (esto me tuvo mal, ya que el inner de cosas como 1011 es un nubmer de un dígito 1)

El resto se basa en estas observaciones:

• x div 10^(digits-1) = el dígito más alto (5445 div 1000 = 5)
• x mod 10^(digits-1) = todos menos el dígito más alto (5445 mod 1000 = 445)
• x mod 10 = el dígito más bajo (5445 mod 10 = 5)
• number div 10 = eliminar el dígito más bajo (5445 div 10 = 544)

solo para estar seguros, probémoslo usando Quickcheck:

Usemos Quickcheck para probarlo (debería ser un buen ejemplo: 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 

parece bien:

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

Si solo se consideran números de cuatro dígitos, puede restar recursivamente 1001 para verificar si el primer y último dígito son iguales y luego restar 0110 para verificar si los dígitos del medio son iguales.

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

Tenga en cuenta que esta función dará resultados incorrectos para números fuera de [1000,9999] rango.

Sección de Reseñas y Valoraciones

Recuerda que puedes difundir esta noticia si te valió la pena.

---

---

Utiliza Nuestro Buscador