0

Necesito crear una función en Haskell, que funcione de la siguiente manera

periodicidad :: [Integer] -> [Integer]
periodicidad [1,2,3,4,1,2,3,4...] = [1,2,3,4]
periodicidad [0,1,2,5,4,3,0,1,2,5,4...] = [0,1,2,5,4,3]

Es decir, que de una lista te extraiga la parte que siempre se va reptiendo, lo que en Ciencias Matemáticas se denominaría periodo de una función.

He intentado agrupar mediante group y cycle, pero no consigo nada. Espero que me puedan ayudar, estoy atascado y no sé qué hacer.

2 respuestas 2

1

Puedes obtener todas las sublistas desde la cabeza con la función inits:

inits [1,2,1,2]
[[],[1],[1,2],[1,2,1],[1,2,1,2]]

Dado que la lista vacía no nos interesa, la quitamos con la función tail, que devuelve la cola de la lista:

tail [[],[1],[1,2],[1,2,1],[1,2,1,2]]
[[1],[1,2],[1,2,1],[1,2,1,2]]

Ahora filtramos de esta lista, con la función filter, las listas cuyo ciclo sean iguales a la lista original:

filter (\x -> take (length [1,2,1,2]) (cycle x) == [1,2,1,2]) [[1],[1,2],[1,2,1],[1,2,1,2]]
[[1,2],[1,2,1,2]]

Finalmente, cogemos la primera lista que cumpla dicha condición con la función head:

head [[1,2],[1,2,1,2]]
[1,2]

Juntándolo todo en una función:

import Data.List(inits)
period :: Eq a => [a] -> [a]
period xs = head $ filter (\x -> take (length xs) (cycle x) == xs) $ tail $ inits xs 

Por ejemplo:

period [1,2,3,1,2,3,1,2,3]
[1,2,3]

period [1,2,1,2,1,2,1]
[1,2]
0

Suponiendo que estamos seguros que la lista tiene un periodo, basta con saber cuándo la primera parte de la lista es prefijo del resto. Para esto tenemos las funciones inits y tails que nos dan todas las partes iniciales y todas las finales, por lo que bastará con comparararlas:

import Data.List (inits, tails, isPrefixOf)

periodo :: [Integer] -> [Integer]
periodo xs = head [ys | (ys,zs) <- tail (zip (inits xs) (tails xs))
                      , ys `isPrefixOf` zs]

El tail es para evitar el primer caso, ([],xs), ya que nos daría un caso falso.

Aunque así funciona en general, falla cuando no existe un periodo (eg: [1..10])

Podemos dar una definición más robusta, asegurando que el periodo se repite en todo el resto de la lista:

import Data.List (inits, tails, isPrefixOf, cycle)
import Data.Maybe (listToMaybe)

periodo :: Eq a => [a] -> Maybe [a]
periodo xs =
  listToMaybe
     [ys | (ys,zs) <- tail (zip (inits xs) (tails xs))
         , zs `isPrefixOf` cycle ys
         , (not.null) zs]

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.