¿Por qué el siguiente código Haskell no termina:¿Por qué este código Haskell no termina?
foldr (||) True $ repeat False -- never terminates
cuando algo como esto hace:
foldr (||) False $ repeat True -- => True
Para mí, es la segunda expresión que parece estar en más problemas de los que no termina. ¿Qué pasa con mi opinión sobre la evaluación perezosa de Haskell?
Creo que su comprensión de lazy es correcta, pero no para foldr. Veamos su "specification"
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
luego ver su expresión
foldr (||) True $ repeat False -- never terminates
Como se ve el True (z) que estamos "buscando" para obtener || dar por terminado no será alcanzado hasta que se consuma toda la lista. Y eso no sucederá ya que la lista es infinita.
Esto también debería explicar el ejemplo de terminación real.
De hecho, estaba malinterpretando foldr, no evaluación perezosa! –
La primera se amplía a False || (False || (False || ...)), mientras que la segunda se amplía a True || (True || (True || ...)). El segundo argumento para foldr es una pista falsa: aparece en la aplicación más interna de ||, no la más externa, por lo que nunca puede ser alcanzada.
El problema es bastante obvio, si desplegar el foldr manualmente:
foldr (||) True $ repeat False == False || (False || (False (False || ... True)))
Así que con el fin de obtener la última False, el código tenía que evaluar la lista hasta su fin (no existente). En su segundo ejemplo, repite True, por lo que es posible la evaluación de cortocircuito. ¡No esperes magia de la evaluación perezosa!
Has cambiado True y False en el despliegue. –
@Daniel Gracias. Es demasiado tarde aquí en Berlín ... – fuz
Una otra visión para usted es que || no es conmutativa en Haskell, es sesgada :
Prelude> undefined || True
*** Exception: Prelude.undefined
Prelude> True || undefined
True
Así que a diferencia de las matemáticas, y ||flip (||) son diferentes funciones. P.ej. comparar
foldr (||) False $ repeat True y foldr (flip (||)) False $ repeat True
El primero termina, pero este último no lo hacen.
Gracias. ¡Esa es de hecho otra sorpresa para mí! –
siempre puede usar stepeval para este tipo de problemas. lleva un segundo descifrar, pero puede ser útil. http://bm380.user.srcf.net/cgi-bin/stepeval.cgi?expr=foldr+%28%7C%7C%29+True+%24+repeat+False – gatoatigrado
Escribí stepeval, y no está evaluando esa expresión ¡correctamente! Tiene algunos errores, me temo (en este caso, se olvida del "dejar" aunque todavía lo necesite) –