¿Está optimizada mi función de foldl reescrita?

Question

Acabo de iniciar Haskell hace 2 días, por lo que aún no estoy seguro de cómo optimizar mi código.

A modo de ejercicio, he reescrito foldl y foldr (I dará foldl aquí, pero foldr que es lo mismo, en sustitución de last con head y init con tail).

El código es:

module Main where 

    myFoldl :: (a -> (b -> a)) -> a -> ([b] -> a) 

    myFoldl func = (\x -> (\theList 
     -> if (length theList == 0) then 
      x 
     else 
      myFoldl func (func x (last theList)) (init theList) 
     )) 

Mi única preocupación es que sospecho Haskell no se puede aplicar la optimización de llamada de cola aquí porque la llamada recursiva no se hace al final de la función.

¿Cómo puedo optimizar esta llamada? ¿La implementación incorporada de Haskell de foldl se implementó de manera diferente a la mía?

Answer 1

El uso de paréntesis en la muestra de código y su énfasis en la recursividad de cola sugiere que está llegando a Haskell desde Lisp o Scheme. Si vienes a Haskell desde un lenguaje entusiasta como Scheme, ten en cuenta que las llamadas de cola no son tan predictivas de rendimiento en Haskell como lo son en un lenguaje entusiasta. Puede tener funciones recursivas de cola que se ejecutan en el espacio lineal debido a la pereza, y puede tener funciones recursivas sin cola que se ejecutan en un espacio constante debido a la pereza. (¿Confundido ya?)

El primer defecto en su definición es el uso del length theList == 0. Esto fuerza la evaluación de toda la columna vertebral de la lista, y es el tiempo O (n). Es mejor utilizar la coincidencia de patrones, como en este foldl definición ingenua en Haskell:

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f z [] = z 
foldl f z (x:xs) = foldl f (f z x) xs 

Esto, sin embargo, lleva a cabo infame mal en Haskell, porque en realidad no calculamos la parte f z x hasta que la persona que llama de foldl exige la resultado; entonces este foldl acumula thunks no evaluados en memoria para cada elemento de lista, y no obtiene ningún beneficio de ser recursivo de cola. De hecho, a pesar de ser recursivo de cola, este ingenuo foldl en una larga lista puede provocar un desbordamiento de la pila. (El Data.List module tiene una función foldl' que no tiene este problema.)

Como respuesta a esto, muchas funciones recursivas no cola Haskell funcionan muy bien. Por ejemplo, tomar esta definición de find, basado en la definición recursiva no acompaña la cola de foldr:

find :: (a -> Boolean) -> [a] -> Maybe a 
find pred xs = foldr find' Nothing xs 
    where find' elem rest = if pred elem then Just elem else rest 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (subfold xs) 
    where subfold = foldr f z 

Esto ejecuta realmente en el tiempo lineal y el espacio constante, gracias a la pereza. ¿Por qué?

1. Una vez que encuentre un elemento que satisface el predicado, no hay necesidad de recorrer el resto de la lista para calcular el valor de rest.
2. Una vez que observa un elemento y decide que no coincide, no es necesario que conserve ningún dato sobre ese elemento.

La lección que impartiría en este momento es: no traiga sus suposiciones de rendimiento de los idiomas ansiosos en Haskell. Estás solo dos días adentro; concéntrese primero en comprender la sintaxis y la semántica del lenguaje, y no se contornee escribiendo versiones optimizadas de funciones todavía. Al principio, te golpearán con el desbordamiento de la pila de estilo foldl, pero lo dominarás a tiempo.

---

EDITAR [9/5/2012]: manifestación más simple que perezosos find carreras en el espacio constante a pesar de no ser recursiva cola. Definiciones En primer lugar, simplificadas:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (foldr f z xs) 

find :: (a -> Bool) -> [a] -> Maybe a 
find p xs = let step x rest = if p x then Just x else rest 
      in foldr step Nothing xs 

Ahora, utilizando el razonamiento ecuacional (es decir, sustituyendo iguales con iguales, basado en la definición anterior), y evaluar en un orden perezosa (más externa en primer lugar), vamos a calcular find (==400) [1..]:

find (==400) [1..] 
    -- Definition of `find`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [1..] 

    -- `[x, y, ...]` is the same as `x:[y, ...]`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (1:[2..]) 

    -- Using the second equation in the definition of `foldr`: 
    => let step x rest = if x == 400 then Just x else rest 
     in step 1 (foldr step Nothing [2..]) 

    -- Applying `step`: 
    => let step x rest = if x == 400 then Just x else rest 
     in if 1 == 400 then Just 1 else foldr step Nothing [2..] 

    -- `1 == 400` is `False` 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 1 else foldr step Nothing [2..] 

    -- `if False then a else b` is the same as `b` 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [2..] 

    -- Repeat the same reasoning steps as above 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (2:[3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 2 (foldr step Nothing [3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 2 == 400 then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [3..] 
     . 
     . 
     . 

    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [400..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (400:[401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 400 (foldr step Nothing [401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 400 == 400 then Just 400 else foldr step Nothing [401..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if True then Just 400 else foldr step Nothing [401..] 

    -- `if True then a else b` is the same as `a` 
    => let step x rest = if x == 400 then Just x else rest 
     in Just 400 

    -- We can eliminate the `let ... in ...` here: 
    => Just 400 

Tenga en cuenta que las expresiones en los sucesivos pasos de evaluación no se vuelven progresivamente más complejas o más largas a medida que avanzamos por la lista; la longitud o profundidad de la expresión en el paso n no es proporcional a n, es básicamente fija. De hecho, esto demuestra cómo find (==400) [1..] se puede ejecutar de forma perezosa en un espacio constante.

Answer 2

Idiomatic Haskell se ve muy diferente a esto, evitando if-then-else, lambdas anidados, paréntesis y funciones de desestructuración (cabeza, cola). En su lugar, iba a escribir algo así como:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = go z0 xs0 
    where 
     go z []  = z 
     go z (x:xs) = go (f z x) xs 

sino que confía en concordancia con el modelo, una cláusula WHERE, la recursión de cola, vigilado declaraciones.