haskell - ¿Es preferible foldl a su primo estricto, foldl ''?

foldl in haskell

Question

Haskell tiene dos funciones de plegado a la izquierda para listas: foldl , y una versión "estricta", foldl'' . El problema con el foldl no estricto es que construye una torre de troncos:

    foldl (+) 0 [1..5]
--> ((((0 + 1) + 2) + 3) + 4) + 5
--> 15

Esto desperdicia memoria y puede causar un desbordamiento de pila si la lista tiene demasiados elementos. foldl'' , por otro lado, fuerza el acumulador en cada artículo.

Sin embargo, por lo que puedo decir, foldl'' es semánticamente equivalente a foldl . La evaluación de foldl (+) 0 [1..5] para encabezar la forma normal requiere forzar el acumulador en algún punto. Si no necesitáramos una forma normal de cabeza, no estaríamos evaluando foldl (+) 0 [1..5] para empezar.

¿Hay alguna razón convincente por la que uno quisiera el comportamiento de foldl sobre el de foldl'' ?

Answer 1

Cuando foldl y foldl'' no producirían el mismo resultado, como en el ejemplo de hammar, la decisión debe tomarse de acuerdo con el resultado deseado. Aparte de eso, usaría foldl lugar de foldl'' si la función folded es un constructor (la aplicación de un constructor crea un valor en WHNF, no tiene sentido forzarlo a WHNF de nuevo), y en foldl (.) id functions donde forzar a WHNF tampoco gana nada. Aparte de estos casos excepcionales, foldl'' es el método de elección.

Answer 2

foldl y foldl'' no son semánticamente equivalentes. Contraejemplo trivial:

Prelude Data.List> foldl (/x y -> y) 0 [undefined, 1]
1
Prelude Data.List> foldl'' (/x y -> y) 0 [undefined, 1]
*** Exception: Prelude.undefined

Sin embargo, en la práctica, por lo general, usted desea el foldl'' estricto por los motivos que mencionó.