-- ---------------------------------------------------------------------
-- § Librerías auxiliares --
-- ---------------------------------------------------------------------
import Data.List
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- § Tipos --
-- ---------------------------------------------------------------------
-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)
-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])
-- ---------------------------------------------------------------------
-- § De racional a decimal --
-- ---------------------------------------------------------------------
-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
-- mayorExponente 2 40 == 3
-- mayorExponente 5 40 == 1
-- mayorExponente 5 41 == 0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1
-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo,
-- longitudAnteperiodo 2 == 1
-- longitudAnteperiodo 3 == 0
-- longitudAnteperiodo 14 == 1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)
-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo,
-- longitudPeriodo 2 == 0
-- longitudPeriodo 3 == 1
-- longitudPeriodo 7 == 6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
| m == 1 = 0
| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))
-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,
-- take 10 (expansionDec (1,4)) == [0,2,5]
-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]
-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]
-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y)
| r == 0 = [q]
| otherwise = q : expansionDec (r*10,y)
where (q,r) = quotRem x y
-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
-- parteEntera (125,3) == 41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b
-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
-- antePeriodo (23,14) == [6]
-- antePeriodo (1,5) == [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
where xs = expansionDec (a,b)
s = longitudAnteperiodo b
-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que
-- se encuentran entre la parte entera y el primer período de a/b. Por
-- ejemplo,
-- periodo (1,3) == [3]
-- periodo (1,5) == []
-- periodo (1,7) == [1,4,2,8,5,7]
-- periodo (23,14) == [4,2,8,5,7,1]
-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
where xs = expansionDec (a,b)
s = longitudAnteperiodo b
t = longitudPeriodo b
-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo,
-- reducido (40,80) == (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m)
where m = gcd a b
-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo,
-- decimal (1,4) == (0,[2,5],[])
-- decimal (1,3) == (0,[],[3])
-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
where r = reducido (a,b)
-- ---------------------------------------------------------------------
-- § De decimal a racional --
-- ---------------------------------------------------------------------
-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
-- digitosAnumero [3,2,5] == 325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0
-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
where n = length xs
-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
-- racional (0,[2,5],[]) == (1,4)
-- racional (0,[],[3]) == (1,3)
-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
a = digitosAnumero (x:ys)
b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where
a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)
-- ---------------------------------------------------------------------
-- § Propiedades --
-- ---------------------------------------------------------------------
-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
a >= 0 && b > 0 ==>
racional (decimal (a,b)) == reducido (a,b)
-- La comprobación es
-- ghci> quickCheck prop_RacionalDecimal
-- +++ OK, passed 100 tests.
-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
b <- arbitrary
return (reducido (abs a, 1+ abs b))
-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
forAll numeroRacional
(\(a,b) -> racional (decimal (a,b)) == (a,b))
-- La comprobación es
-- ghci> quickCheck prop_RacionalDecimal2
-- +++ OK, passed 100 tests.
-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
b <- arbitrary
return (decimal (abs a, 1+ abs b))
-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
forAll numeroDecimal
(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))
-- La comprobación es
-- ghci> quickCheck prop_DecimalRacional
-- +++ OK, passed 100 tests. |
José A. Alonso