Tratar con (los riesgos de) secuencias infinitas en Haskell

7

Estoy a un par de semanas de incursionar con haskell y he hecho una gran mella en Learn You A Haskell. Siento que muchas de las clases de tipos y las implementaciones comunes hasta los aplicativos y las mónadas tienen mucho sentido para mí y entiendo cómo funcionan, pero todavía me falta mucha experiencia práctica.

Una cosa que me molesta, que proviene de un fondo fundamentalmente imperativo / OOP es el concepto de valores / funciones que se evalúan en listas infinitas. Por supuesto, puedo ver cómo se pueden usar para escribir algunas definiciones de forma muy concisa y seguramente son útiles en muchos casos que ni siquiera puedo imaginar. Me pregunto cuál es el enfoque común para mitigar sus riesgos. Si en algún punto de su código evalúa accidentalmente una lista infinita "completamente", su programa simplemente se atascará. Por supuesto, esto también se puede hacer en lenguajes imperativos (ciertas implementaciones de las interfaces IEnumerable / Iterator de C # / Java, por ejemplo), pero es mi experiencia que la gente rara vez hace esto porque es ... bueno, peligroso.

Una de las grandes ventajas de Haskell son los controles de tiempo de compilación que obtiene. ¿Podemos hacer controles de tiempo de compilación para hacer frente a este riesgo? ¿O escribimos pruebas para ello? ¿O simplemente "nunca somos lo suficientemente estúpidos para hacer eso, y si lo hacemos, lo notamos después de 1 segundo cuando lo ejecutamos en el REPL"? ¿O hay convenciones de nombramiento?

Me doy cuenta de que esto es probablemente un poco subjetivo, pero ¿seguramente hay modismos comunes?

    
pregunta sara 27.04.2016 - 09:30

3 respuestas

5

Este riesgo de producir accidentalmente una lista infinita es lo mismo que tener accidentalmente un bucle sin fin. La única diferencia es que en configuraciones perezosas puede que no se manifieste en absoluto (si no evalúa toda la estructura), y si lo hace, estará en un lugar diferente, lo que puede ser más difícil de depurar.

Una opción es usar estructuras de datos finitos por la fuerza como Vector o Seq . Si desea utilizar listas vinculadas, puede definir una con una columna vertebral estricta como

data List a = Nil | Cons a !(List a)

Aunque actualmente Haskell no hace eso, hay un concepto de Programación Funcional Total que permite garantizar por sintáctico Comprueba que todos los cálculos terminan. En particular, evita la creación de estructuras de datos infinitas (datos) o, alternativamente, les permite, pero el desenvolvimiento de un nivel siempre termina ( codata ).

    
respondido por el Petr Pudlák 27.04.2016 - 19:17
3

Creo que una buena regla general aquí es: manténgase alejado de las operaciones que divergen en estructuras infinitas . Eso no significa que nunca los use, sino que difiere su uso en la medida de lo posible en su programa.

Se necesita un poco de experiencia para aprender a reconocer estas operaciones, pero eso viene con el tiempo. Algunos ejemplos son length , sum y foldl' ; y un hecho útil es que a menudo se puede evitar la divergencia al cambiar de estas a operaciones basadas en scanl . Por ejemplo, la función para tomar la suma de todos los números en una lista se desviará hacia listas infinitas:

sum :: Num a => [a] -> a
sum = foldl' (+) 0

-- 'sum [1..]' diverges...

Pero la función para calcular las sumas de todos los prefijos de una lista funciona bien con listas infinitas:

sums :: Num a => [a] -> a
sums = scanl' (+) 0

-- 'take 10 (sums [1..])' => '[0,1,3,6,10,15,21,28,36,45]'

Pero como jozefg señala en un comentario, otra forma común de evitar estos problemas es usar tipos de datos que solo admiten colecciones finitas. Las listas de Haskell se usan ampliamente, pero también lo son Map , Set , Vector , ByteString y Text , todas ellas con garantía finita, y cada una ofrece algunas características o concesiones diferentes a lo que hacen las listas. Esto llega a tu última pregunta:

  

Una de las grandes ventajas de Haskell son los controles de tiempo de compilación que obtiene. ¿Podemos hacer controles de tiempo de compilación para hacer frente a este riesgo?

Sí, puede hacer esto utilizando algún otro tipo de datos que garantice la finitud. No dude en probar cualquiera de los que mencioné anteriormente.

    
respondido por el sacundim 11.05.2016 - 00:58
-1

En un lenguaje perezoso, es mucho más difícil evaluar una lista infinita por completo, a menos que esté utilizando funciones explícitamente estrictas (por ejemplo, seq o funciones que se implementan al usarla, como foldl '). Si se mantiene alejado de estos, solo se generarán las entradas que sean relevantes para calcular su salida. Por lo tanto, siempre y cuando continúe procesando listas potencialmente infinitas con foldr, map and take, probablemente nunca tendrá un problema.

    
respondido por el Jules 27.04.2016 - 10:14

Lea otras preguntas en las etiquetas