iteradores - python yield explicacion

¿Es la pereza de Haskell una alternativa elegante a los generadores de Python?

Question

En un ejercicio de programación, primero se le pidió programar la función factorial y luego calcular la suma: 1! + 2! + 3! +... n! 1! + 2! + 3! +... n! en O(n) multiplicaciones (por lo que no podemos usar el factorial directamente). No estoy buscando la solución a este problema específico (trivial), estoy tratando de explorar las habilidades de Haskell y este problema es un juguete con el que me gustaría jugar.

Pensé que los generadores de Python podrían ser una buena solución para este problema. Por ejemplo :

from itertools import islice
def ifact():
    i , f = 1, 1
    yield 1
    while True:
        f *= i
        i += 1
        yield f

def sum_fact(n):
    return sum(islice(ifact(),5))

Luego traté de averiguar si había algo en Haskell con un comportamiento similar al de este generador y pensé que la pereza hace que todo el personal se quede sin ningún concepto adicional.

Por ejemplo, podríamos reemplazar mi ifact Python con

fact = scan1 (*) [1..]

Y luego resuelve el ejercicio con lo siguiente:

sum n = foldl1 (+) (take n fact)

Me pregunto si esta solución es realmente "equivalente" a la de Python con respecto a la complejidad del tiempo y el uso de la memoria. Yo diría que la solución de Haskell nunca almacena toda la información de la lista, ya que sus elementos se usan solo una vez.

¿Estoy en lo correcto o totalmente equivocado?

EDITAR: Debería haber comprobado más precisamente:

Prelude> foldl1 (+) (take 4 fact)
33
Prelude> :sprint fact
fact = 1 : 2 : 6 : 24 : _

Entonces (mi implementación de) Haskell almacena el resultado, incluso si ya no se usa.

Answer 1

Básicamente, sí: las listas perezosas de Haskell son muy parecidas a los generadores de Python, si esos generadores fueran clonables, almacenables y compensables. En lugar de elevar StopIteration , devuelve [] desde su función recursiva, que puede enlazar el estado al generador.

Hacen algunas cosas más interesantes debido a la auto-recursión. Por ejemplo, su generador factorial se genera más idiomáticamente como:

facts = 1 : zipWith (*) facts [1..]

o la Fibonaccis como:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

En general, cualquier bucle iterativo se puede convertir en un algoritmo recursivo promoviendo el estado del bucle a los argumentos de una función y luego llamándolo recursivamente para obtener el siguiente ciclo de bucle. Los generadores son así, pero añadimos algunos elementos a cada iteración de la función recursiva, `go ____ = (cosas): go ____.

El equivalente perfecto es por lo tanto:

ifact :: [Integer]
ifact = go 1 1
  where go f i = f : go (f * i) (i + 1)

sum_fact n = sum (take n ifact)

En términos de lo que es más rápido, el más rápido en Haskell probablemente será el "for loop":

sum_fact n = go 1 1 1
  where go acc fact i
          | i <= n = go (acc + fact) (fact * i) (i + 1)
          | otherwise = acc

El hecho de que esto sea "recursivo de cola" (una llamada de go no canaliza ninguna sub llamada para go a otra función como (+) o (*) ) significa que el compilador puede empaquetarlo en un bucle muy ajustado, y por eso lo comparo con "for loops", aunque en realidad no es una idea nativa de Haskell.

El sum_fact n = sum (take n ifact) es un poco más lento que esto, pero más rápido que la sum (take n facts) donde los facts se definen con zipWith . Las diferencias de velocidad no son muy grandes y creo que en su mayoría solo se trata de asignaciones de memoria que no se vuelven a utilizar.

Answer 2

De hecho, las listas perezosas pueden usarse de esta manera. Sin embargo, hay algunas diferencias sutiles:

• Las listas son estructuras de datos. Así que puede mantenerlos después de evaluarlos, lo que puede ser bueno o malo (puede evitar la recálculo de valores y los trucos recursivos como se describe en @ChrisDrost, a costa de mantener la memoria sin liberar).
• Las listas son puras. En los generadores puede tener cálculos con efectos secundarios, no puede hacer eso con listas (lo que a menudo es deseable).
• Dado que Haskell es un lenguaje perezoso, la pereza está en todas partes y si simplemente convierte un programa de un lenguaje imperativo a Haskell, los requisitos de memoria pueden cambiar considerablemente (como lo describe @RomanL en su respuesta).

Pero Haskell ofrece herramientas más avanzadas para lograr el patrón generador / consumidor. Actualmente hay tres bibliotecas que se centran en este problema: tuberías, conductos e iteraciones . Mi favorito es el conduit , es fácil de usar y la complejidad de sus tipos se mantiene baja.

Tienen varias ventajas, en particular que puede crear tuberías complejas y puede basarlas en una mónada elegida, lo que le permite decir qué efectos secundarios están permitidos en una tubería.

Usando conductos, su ejemplo podría expresarse como sigue:

import Data.Functor.Identity
import Data.Conduit
import qualified Data.Conduit.List as C

ifactC :: (Num a, Monad m) => Producer m a
ifactC = loop 1 1
  where
    loop r n = let r'' = r * n
                in yield r'' >> loop r'' (n + 1)

sumC :: (Num a, Monad m) => Consumer a m a
sumC = C.fold (+) 0

main :: IO ()
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC)
-- alternatively running the pipeline in IO monad directly:
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print

Aquí creamos un Producer (un conducto que no consume entrada) que produce factoriales indefinidamente. Luego lo componemos con isolate , lo que garantiza que no se propague más de un número determinado de valores a través de él, y luego lo componemos con un Consumer que solo suma valores y devuelve el resultado.

Answer 3

Sus ejemplos no son equivalentes en el uso de la memoria. Es fácil ver si reemplaza * con un + (para que los números no crezcan demasiado rápido) y luego ejecute ambos ejemplos en una gran n como 10 ^ 7. Tu versión de Haskell consumirá mucha memoria y Python la mantendrá baja.

El generador de Python no generará una lista de valores y luego la resumirá. En su lugar, la función de sum obtendrá valores uno por uno del generador y los acumulará. Por lo tanto, el uso de la memoria se mantendrá constante.

Haskell evaluará las funciones con pereza, pero para calcular, digamos, foldl1 (+) (take n fact) tendrá que evaluar la expresión completa. Para n grande, esto se convertirá en una expresión enorme de la misma manera que lo hace (foldl (+) 0 [0..n]) . Para obtener más detalles sobre la evaluación y la reducción, consulte aquí: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 .

Puede corregir su sum n usando foldl1'' lugar de foldl1 como se describe en el enlace anterior. Como @ user2407038 explicó en su comentario, también necesitaría mantener el fact local. Los siguientes trabajos en GHC con un uso de memoria constante:

let notfact = scanl1 (+) [1..]
let n = 20000000
let res = foldl'' (+) 0 (take n notfact)

Tenga en cuenta que en el caso del factorial real en lugar de las consideraciones de memoria no son menos preocupantes. Los números crecerán rápidamente, la aritmética de precisión arbitraria hará que las cosas sean más lentas, por lo que no podrá obtener grandes valores de n para ver la diferencia.