¿Cuándo puedo confiar en Haskell para leer una lista perezosamente?

8

¿Por qué recibo un <<loop>>error de tiempo de ejecución de bucle infinito ( ) aquí?

archivo feedback.hs:

plus1 :: [Int]->[Int] -- add 1 to input stream
plus1 [] = []
plus1 (x:xs) = (x+1): plus1 xs

to10 :: [Int] -> [Int] -- stop the input stream when it gets to 10
to10 (x:xs) | x < 10 = x : to10 xs
            | otherwise = []

to10plus :: [Int] -> ([Int], Int) -- like to10 but also return the count
to10plus (x:xs) | x < 10 = (x, 1) `merge` (to10plus xs)
            | otherwise = ([], 0)
  where merge (a, b) (as, bs) = (a:as, b+bs)

main = do
  let out = plus1 $ 1: to10 out
  putStrLn $ show out -- gives [2,3,4,5,6,7,8,9,10]


  let out = plus1 $ 1: out2
      out2 = to10 out
  putStrLn $ show out -- same as above

  let out = plus1 $ 1: out2
      (out2, count) = to10plus out
  putStrLn $ show (out, count) -- expect ([2,3,4,5,6,7,8,9,10], 8) 
                               -- but get runtime error: <<loop>>
$ ghc feedback.hs 
[1 of 1] Compiling Main             ( feedback.hs, feedback.o )
Linking feedback ...
$ ./feedback
[2,3,4,5,6,7,8,9,10]
[2,3,4,5,6,7,8,9,10]
feedback: <<loop>>
Daniel Patru
fuente

Respuestas:

7

Puede solucionarlo to10plususando una coincidencia irrefutable (es decir, un ~prefijo) en su definición de merge:

merge (a, b) ~(as, bs) = (a:as, b+bs)

La razón de la diferencia en el comportamiento entre to10y to10pluses que to10puede devolver el primer elemento de la lista sin tener que evaluar to10 xsy así sin inspeccionar xs.

Por el contrario, antes de que pueda devolver algo, to10plusdebe llamar mergecon éxito con los argumentos (x, 1)y to10plus xs. Para que esta llamada to10plus xstenga éxito, debe evaluarse lo suficiente como para garantizar que coincida con el patrón (as, bs)utilizado en la definición de merge, pero esa evaluación requiere la inspección de elementos de xs, que aún no están disponibles.

También podría haber evitado el problema definiendo to10plusun poco diferente:

to10plus (x:xs) | x < 10 = (x:as,1+bs)
                | otherwise = ([], 0)
  where (as,bs) = to10plus xs

Aquí, to10pluspuede proporcionar el primer elemento xde la primera parte de la tupla sin intentar evaluar as, y así sin tratar de coincidir to10plus xscon el patrón (as,bs)en la wherecláusula. Una letcláusula habría hecho lo mismo:

to10plus (x:xs) | x < 10 = let (as,bs) = to10plus xs in (x:as,1+bs)
                | otherwise = ([], 0)

Como señala @luqui, esta es una diferencia en el tiempo para las coincidencias de patrones realizadas por lety wheredeclaraciones:

let (a,b) = expr in body
-- OR --
body where (a,b) = expr

versus casedeclaraciones / definiciones de funciones:

case expr of (a,b) -> body
-- OR --
f (a,b) = body  -- AND THEN EVALUATING: -- f expr

Las declaraciones lety wherecoinciden con los patrones de manera perezosa, lo que significa que exprno coinciden con el patrón (a,b)hasta que ao bse evalúan en el body. Por el contrario, para la casedeclaración, exprse compara de (a,b)inmediato, bodyincluso antes de que se examine. Y dada la definición anterior de f, el argumento to fserá comparado (a,b)tan pronto como f exprse evalúe la expresión sin esperar hasta ao bsea ​​necesaria en la función body. Aquí hay algunos ejemplos de trabajo para ilustrar:

ex1 = let (a,b) = undefined in print "okay"
ex2 = print "also okay" where (a,b) = undefined
ex3 = case undefined of (a,b) -> print "not okay"
ex4 = f undefined
f (a,b) = print "also not okay"

main = do
  ex1   -- works
  ex2   -- works
  ex3   -- fails
  ex4   -- fails

Adición de ~cambios del comportamiento para caselas definiciones de funciones / por lo que el juego se lleva a cabo sólo cuando ao bse necesitan para:

ex5 = case undefined of ~(a,b) -> print "works fine"
ex6 = g undefined
g ~(a,b) = print "also works fine"

ex7 = case undefined of ~(a,b) -> print $ "But trying " ++ show (a+b) ++ " would fail"
KA Buhr
fuente
3
La diferencia clave está lejos de ser evidente y probablemente debería establecerse: el patrón coincide lety wheresiempre es vago, pero los patrones para los argumentos son por defecto estrictos a menos que se hagan vagos ~.
luqui
Gracias KA Buhr y luqui!
Daniel Patru