listas - ¿Puedes reconocer una lista infinita en un programa de Haskell?

listas infinitas haskell

Question

Posible duplicado:
¿Cómo saber si una lista es infinita?

En Haskell, puede definir una lista infinita, por ejemplo [1..] . ¿Hay una función incorporada en Haskell para reconocer si una lista tiene una longitud finita? No creo que sea posible escribir una función suministrada por el usuario para hacer esto, pero la representación interna de las listas de Haskell puede ser compatible con ella. Si no está en el estándar Haskell, ¿hay una extensión que proporcione tal característica?

Answer 1

Como escribió Ehird, su única esperanza es descubrir si una lista es cíclica. Una forma de hacerlo es usar una extensión de Haskell llamada "intercambio observable". Ver por ejemplo: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4053

Answer 2

Cuando se habla de "representación interna de listas", desde el punto de vista de la implementación de Haskell, no hay listas infinitas. La "lista" sobre la que pregunta es en realidad una descripción del proceso computacional, no un objeto de datos. Ningún objeto de datos es infinito dentro de una computadora. Tal cosa simplemente no existe.

Como otros lo han dicho, los datos de la lista interna pueden ser cíclicos, y la implementación generalmente podría detectar esto, teniendo un concepto de igualdad de puntero. Pero el propio Haskell no tiene tal concepto.

Aquí hay una función Common Lisp para detectar la ciclicidad de una lista. cdr avanza a lo largo de una lista por una muesca, y cddr - por dos. eq es un predicado de igualdad de puntero.

(defun is-cyclical (p)
  (labels ((go (p q) 
             (if (not (null q)) 
               (if (eq p q) t 
                 (go (cdr p) (cddr q))))))
    (go p (cdr p))))

Answer 3

No hay ninguna manera de probar la finitud de las listas que no sea iterar sobre la lista para buscar el final [] en cualquier implementación que conozca. Y, en general, es imposible saber si una lista es finita o infinita sin buscar realmente el final (lo que por supuesto significa que cada vez que recibes una respuesta, eso dice finito).

Answer 4

No, esto no es posible. Sería imposible escribir una función de este tipo, ya que puede tener listas cuya finitud podría ser desconocida: considere un ciclo recursivo que genere una lista de todos los números primos gemelos que puede encontrar. O, para hacer un seguimiento de lo que Daniel Pratt mencionó en los comentarios, podría tener una lista de todos los pasos que toma una máquina universal de Turing durante su ejecución, finalizando la lista cuando la máquina se detiene. Luego, simplemente puede verificar si dicha lista es infinita y resolver el problema de la detención .

La única pregunta que una implementación podría responder es si una lista es cíclica: si uno de sus punteros de cola apunta a una celda anterior de la lista. Sin embargo, esto es específico de la implementación (Haskell no especifica nada sobre cómo deben representar los valores las implementaciones), impuro (diferentes formas de escribir la misma lista darían respuestas diferentes), e incluso depender de cosas como si la lista a la que se pasa. Tal función ha sido evaluada todavía. ¡Incluso en ese caso, aún no podría distinguir listas finitas de listas infinitas en el caso general!

(Menciono esto porque, en muchos idiomas (como los miembros de la familia Lisp), las listas cíclicas son el único tipo de listas infinitas; no hay forma de expresar algo así como "una lista de todos los enteros". Por lo tanto, en esos idiomas, puedes verificar si una lista es finita o no.)

Answer 5

Podría escribir un tipo de envoltorio alrededor de la lista que haga un seguimiento de la infinitud, y limitarse solo a operaciones "decidibles" (de alguna manera similar a NonEmpty , que evita las listas vacías):

import Control.Applicative

data List a = List (Maybe Int) [a]

infiniteList (List Nothing _) = true
infiniteList _ = false

emptyList = List (Just 0) []
singletonList x = List (Just 1) [x]
cycleList xs = List Nothing (cycle xs)
numbersFromList n = List Nothing [n..] 
appendList (List sx xs)  (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys)
tailList (List s xs) = List (fmap pred s) (tail xs)
...