Antiimagen de función creciente
Una función f de los números naturales en los números naturales es estrictamente creciente si para cualquier par de números x, y tales que x < y se verifica que f(x) < f(y). La antiimagen por f de un número natural t es el número natural x tal que f(x) = t. No todos los números tienen antiimiagen por f, pero en caso de tenerla es única.
Definir la función
antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer
tal que, suponiendo que f es una función creciente de los naturales en los naturales, (antiimagen f t) es justamente la antiimagen por f de t, si existe y es Nothing, en caso contrario. Por ejemplo,
antiimagen (\x -> 2*x^2-3) 47 == Just 5 antiimagen (\x -> 2*x^2-3) 48 == Nothing antiimagen (\x -> 2^x) 1024 == Just 10 antiimagen (2^) 1024 == Just 10 antiimagen (2^) (2^(10^7)) == Just 10000000 antiimagen (2^) (1+2^(10^7)) == Nothing
Soluciones
import Data.Maybe (listToMaybe) -- 1ª solución -- =========== antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen f t = listToMaybe [x | x <- [0..t], f x == t] -- 2ª solución -- =========== antiimagen2 :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen2 f t = busqueda (0,t) where busqueda (a,b) = listToMaybe [x | x <- [a..b], f x == t] -- 3ª solución -- =========== antiimagen3 :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen3 f t = busqueda (0,t) where busqueda (a,b) | a > b = Nothing | t < f m = busqueda (a,m-1) | t == f m = Just m | otherwise = busqueda (m+1,b) where m = (a+b) `div` 2 -- 4ª solución -- =========== antiimagen4 :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen4 f t | f x == t = Just x | otherwise = Nothing where x = busqueda (cotas f t) busqueda (a,b) = head [x | x <- [a+1..b], t <= f x] -- (cotas f t) es un par (a,b) de potencias consecutivas de 2 tal que la -- antiimagen de t por f está en el intevalo [a+1,b]. Por ejemplo, -- cotas (\x -> 2*x^2-3) 47 == (4,8) -- cotas (\x -> 2^x) 1024 == (8,16) cotas :: (Integer -> Integer) -> Integer -> (Integer, Integer) cotas f t | t <= f 0 = (-1,0) | otherwise = (b `div` 2, b) where b = until done (*2) 1 done b = t <= f b -- 5ª solución -- =========== antiimagen5 :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen5 f t | f x == t = Just x | otherwise = Nothing where x = busqueda (cotas f t) busqueda (a,b) | a+1 == b = b | t <= f m = busqueda (a,m) | otherwise = busqueda (m,b) where m = (a+b) `div` 2 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> antiimagen (2^) (2^30) -- Just 30 -- (0.01 secs, 142,728 bytes) -- λ> antiimagen2 (2^) (2^30) -- Just 30 -- (0.01 secs, 142,784 bytes) -- λ> antiimagen3 (2^) (2^30) -- Just 30 -- (8.05 secs, 335,820,048 bytes) -- λ> antiimagen4 (2^) (2^30) -- Just 30 -- (0.01 secs, 133,984 bytes) -- λ> antiimagen5 (2^) (2^30) -- Just 30 -- (0.02 secs, 121,816 bytes) -- -- λ> antiimagen (2^) (2^50000) -- Just 50000 -- (1.29 secs, 673,789,160 bytes) -- λ> antiimagen2 (2^) (2^50000) -- Just 50000 -- (1.28 secs, 673,791,368 bytes) -- λ> antiimagen4 (2^) (2^50000) -- Just 50000 -- (0.84 secs, 342,311,360 bytes) -- λ> antiimagen5 (2^) (2^50000) -- Just 50000 -- (0.01 secs, 549,688 bytes) -- -- λ> antiimagen4 (2^) (2^100000) -- Just 100000 -- (4.37 secs, 1,210,476,848 bytes) -- λ> antiimagen5 (2^) (2^100000) -- Just 100000 -- (0.01 secs, 918,096 bytes)