Antiimágenes en una función creciente

7 Comentarios

1. Haskell

   antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f x = aux f x 1 where aux :: Integral a => (a -> a) -> a -> a -> Maybe a aux f x n | fn < x = aux f x (n+1) | fn == x = Just n | otherwise = Nothing where fn = f n

   1 2 3 4 5 6 7

   antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f x = aux f x 1     where aux :: Integral a => (a -> a) -> a -> a -> Maybe a           aux f x n | fn < x    = aux f x (n+1)                     | fn == x   = Just n                     | otherwise = Nothing                     where fn = f n

   Responder

2. Otra vez usando búsqueda dicotómica sin acotar.

   Haskell

   antiimagen :: (ℤ → ℤ) → ℤ → Maybe ℤ antiimagen f y = arriba 1 where arriba a | f b > y = abajo a b | otherwise = arriba b where b = 2 * a abajo a b | a > b = Nothing | otherwise = case y `compare` f c of EQ → Just c LT → abajo a (c - 1) GT → abajo (c + 1) b where c = (a + b) ÷ 2 -- Por ejemplo, sea la función identidad que "pierde" un nº cada vez a más distancia casiIdentidad x = x + (round ∘ log ∘ fromIntegral) x > antiimagen casiIdentidad 519387222974672466748780267054148298837360341338989753532552 Just 519387222974672466748780267054148298837360341338989753532415 (0.02 secs, 0 bytes) > antiimagen casiIdentidad 519387222974672466748780267054148298837360341338989753532553 Nothing (0.02 secs, 0 bytes) >

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   antiimagen :: (ℤ → ℤ) → ℤ → Maybe ℤ antiimagen f y = arriba 1   where arriba a  | f b > y   = abajo a b                   | otherwise = arriba b                     where b = 2 * a         abajo a b | a > b     = Nothing                   | otherwise = case y `compare` f c of                                   EQ → Just c                                   LT → abajo a (c - 1)                                   GT → abajo (c + 1) b                                 where c = (a + b) ÷ 2       -- Por ejemplo, sea la función identidad que "pierde" un nº cada vez a más distancia casiIdentidad x = x + (round ∘ log ∘ fromIntegral) x   > antiimagen casiIdentidad 519387222974672466748780267054148298837360341338989753532552 Just 519387222974672466748780267054148298837360341338989753532415 (0.02 secs, 0 bytes) > antiimagen casiIdentidad 519387222974672466748780267054148298837360341338989753532553 Nothing (0.02 secs, 0 bytes) >

   Responder

3. Haskell

   import Data.List antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = find (==y) $ takeWhile (<=y) (map f [1..])

   1 2 3 4 5

   import Data.List   antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = find (==y)                $ takeWhile (<=y) (map f [1..])

   Responder

   1. Y ésta es mi versión con búsqueda dicotómica:

      Haskell

      import Data.List antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen f y = bisect f y (lim `div` 2) lim where lim = head [ x | x <- iterate (2*) 1, f x > y ] bisect :: (Integer -> Integer) -> Integer -> Integer -> Integer -> Maybe Integer bisect f y a b | f a == y = Just a | a >= b = Nothing | f m <= y = bisect f y m b | otherwise = bisect f y (a+1) m where m = (a + b) `div` 2

      1 2 3 4 5 6 7 8 9 10 11 12

      import Data.List   antiimagen :: (Integer -> Integer) -> Integer -> Maybe Integer antiimagen f y = bisect f y (lim `div` 2) lim     where lim = head [ x | x <- iterate (2*) 1, f x > y ]   bisect :: (Integer -> Integer) -> Integer -> Integer -> Integer -> Maybe Integer bisect f y a b | f a == y   = Just a                | a >= b     = Nothing                | f m <= y   = bisect f y m b                | otherwise  = bisect f y (a+1) m     where m = (a + b) `div` 2

      Responder

   2. La primera definición falla en el primer ejemplo

      λ> antiimagen (^2) 25 Just 25

      1 2	λ> antiimagen (^2) 25    Just 25

      Responder

      1. Muchas gracias por el apunte. Una versión corregida:

         Haskell

         import Data.List antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = find ((==y).f) $ takeWhile ((<=y).f)[1..]

         1 2 3 4 5

         import Data.List   antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = find ((==y).f)                $ takeWhile ((<=y).f)[1..]

         Se puede mejorar (lo añado como nueva respuesta).

         Responder

4. Haskell

   import Data.List antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = lookup y . takeWhile ((y>=).fst) $ [(f x, x) | x <- [1..]]

   1 2 3 4 5

   import Data.List   antiimagen :: (Int -> Int) -> Int -> Maybe Int antiimagen f y = lookup y . takeWhile ((y>=).fst)                $ [(f x, x) | x <- [1..]]

   Responder