haskell - vale - lenguaje funcional

¿La capacidad de detectar listas cíclicas en Haskell rompería alguna propiedad del idioma?

Question

En Haskell, algunas listas son cíclicas:

ones = 1 : ones

Otros no son:

nums = [1..]

Y luego hay cosas como esta:

more_ones = f 1 where f x = x : f x

Esto denota el mismo valor que ones , y ciertamente ese valor es una secuencia que se repite. Pero es dudoso si está representado en la memoria como una estructura de datos cíclica. (Una implementación podría hacerlo, pero esta respuesta explica que "es poco probable que esto suceda en la práctica" .)

Supongamos que tomamos una implementación de Haskell y isCycle :: [a] -> Bool función isCycle :: [a] -> Bool que examina la estructura de la representación en memoria del argumento. Devuelve True si la lista es físicamente cíclica y False si el argumento es de longitud finita. De lo contrario, no podrá terminar. (Me imagino "hackearlo" porque es imposible escribir esa función en Haskell).

¿La existencia de esta función rompería alguna propiedad interesante del lenguaje?

Answer 1

¿La existencia de esta función rompería alguna propiedad interesante del lenguaje?

Si lo seria Se rompería la transparencia referencial (ver también el artículo de Wikipedia ). Una expresión de Haskell siempre puede ser reemplazada por su valor. En otras palabras, depende solo de los argumentos pasados ​​y nada más. Si tuvieramos

isCycle :: [a] -> Bool

Como propones, las expresiones que lo usan ya no satisfacen esta propiedad. Podrían depender de la memoria interna de la representación de valores. En consecuencia, se violarían otras leyes. Por ejemplo la ley de identidad para Functor

fmap id === id

no se mantendría más: usted podría distinguir entre ones y los fmap id ones , ya que este último sería acíclico. Y las optimizaciones del compilador, como la aplicación de la ley anterior, ya no preservarían las propiedades del programa.

Sin embargo otra cuestión sería tener función.

isCycleIO :: [a] -> IO Bool

Como las acciones de IO se les permite examinar y cambiar cualquier cosa

Una solución pura podría ser tener un tipo de datos que distinga internamente a los dos:

import qualified Data.Foldable as F
data SmartList a = Cyclic [a] | Acyclic [a]
instance Functor SmartList where
fmap f (Cyclic xs) = Cyclic (map f xs)
fmap f (Acyclic xs) = Acyclic (map f xs)
instance F.Foldable SmartList where
foldr f z (Acyclic xs) = F.foldr f z xs
foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r

Por supuesto, no sería capaz de reconocer si una lista genérica es cíclica o no, pero para muchas operaciones sería posible preservar el conocimiento de tener valores Cyclic .

Answer 2

En el caso general, no, no se puede identificar una lista cíclica. Sin embargo, si la lista se genera mediante una operación de despliegue, puede hacerlo. Data.List contiene esto:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

El primer argumento es una función que toma un argumento de "estado" de tipo "b" y puede devolver un elemento de la lista y un nuevo estado. El segundo argumento es el estado inicial. "Nada" significa que la lista termina.

Si el estado vuelve a aparecer, la lista se repetirá desde el punto del último estado. Entonces, si en cambio usamos una función de despliegue diferente que devuelve una lista de (a, b) pares, podemos inspeccionar el estado correspondiente a cada elemento. Si el mismo estado se ve dos veces, entonces la lista es cíclica. Por supuesto, esto supone que el estado es una instancia de Eq o algo así.