Haskell-foldl y foldr?

foldl haskell

Question

¿La diferencia entre foldl y foldr solo la dirección del bucle? Pensé que había una diferencia en lo que hicieron, no solo en la dirección?

Answer 1

Hay una diferencia si su función no es asociativa (es decir, si importa la forma en que se corchetan las expresiones), por ejemplo,
foldr (-) 0 [1..10] = -5 pero foldl (-) 0 [1..10] = -55 .
En una escala pequeña, esto se debe a que 10-(20-(30)) no es lo mismo que ((10)-20)-30 .

Considerando que porque (+) es asociativo (no importa qué orden agregue subexpresiones),
foldr (+) 0 [1..10] = 55 y foldl (+) 0 [1..10] = 55 . (++) es otra operación asociativa porque xs ++ (ys ++ zs) da la misma respuesta que (xs ++ ys) ++ zs (aunque la primera es más rápida, no use foldl (++) .

Algunas funciones solo funcionan de una manera:
foldr (:) :: [a] -> [a] -> [a] pero foldl (:) tiene sentido.

Eche un vistazo a los diagramas de Cale Gibbard (del artículo de wikipedia ); se puede ver a f llamando con pares de datos genuinamente diferentes:

Otra diferencia es que debido a que coincide con la estructura de la lista, foldr suele ser más eficiente para la evaluación perezosa, por lo que se puede usar con una lista infinita siempre que f no sea estricto en su segundo argumento (como (:) o (++) ). foldl rara vez es la mejor opción. Si usas foldl , normalmente vale la pena usar foldl'' porque es estricto y te impide crear una larga lista de resultados intermedios. (Más sobre este tema en las respuestas a esta pregunta .)