¿Cómo escribo una función de longitud de espacio constante en Haskell?

Question

La aplicación canónica de length :: [a] -> Int es:

length [] = 0 
length (x:xs) = 1 + length xs 

que es muy bonito pero sufre de desbordamiento de pila, ya que utiliza el espacio lineal.

La versión recursiva de cola:

length xs = length' xs 0 
    where length' [] n = n 
     length' (x:xs) n = length xs (n + 1) 

no sufren de este problema, pero no entiendo cómo esto puede funcionar en el espacio constante en un lenguaje vago.

¿No es el tiempo de ejecución la acumulación de numerosos (n + 1) thunk mientras se mueve a través de la lista? ¿No debería funcionar esto Haskell para consumir O (n) espacio y conducir al desbordamiento de la pila?

(si importa, estoy usando GHC)

Answer 1

Sí, se ha encontrado con un error común con la acumulación de parámetros. La cura habitual es forzar una evaluación estricta del parámetro de acumulación; para este propósito me gusta el operador de aplicación estricta $!. Si no fuerza el rigor, el optimizador de GHC podría decidir que está bien para que esta función sea estricta, pero podría no ser así. Definitivamente no es una cosa para confiar en — veces quiere un parámetro de acumulación para ser evaluado perezosamente y O (N) espacio está bien, gracias.

¿Cómo escribo una función de longitud de espacio constante en Haskell?

Como se señaló anteriormente, utilice el operador aplicación estricta para forzar la evaluación del parámetro de acumulación:

clength xs = length' xs 0 
    where length' []  n = n 
     length' (x:xs) n = length' xs $! (n + 1) 

El tipo de $! es (a -> b) -> a -> b, y que obliga a la evaluación de la a antes de aplicar la función.

Answer 2

Una función recursiva de cola no necesita para mantener una pila, ya que el valor devuelto por la función va a ser simplemente el valor devuelto por el llamada de cola. Entonces, en lugar de crear un nuevo marco de pila, el actual se reutiliza, con los locales sobrescritos por los nuevos valores pasados ​​a la llamada final. Por lo tanto, cada n+1 se escribe en el mismo lugar donde estaba el antiguo n, y tiene un uso de espacio constante.

Editar - En realidad, como usted lo ha escrito, tiene razón, se thunk el (n+1) s y causar un desbordamiento. Fácil de probar, solo intente length [1..1000000]. Puede solucionarlo forzándolo a evaluarlo primero: length xs $! (n+1), que luego funcionará como dije anteriormente.

Answer 3

El funcionamiento de su segunda versión en GHCi:

> length [1..1000000] 
*** Exception: stack overflow 

Así que para responder a su pregunta: Sí, sufre de ese problema, al igual que usted espera.

Sin embargo, GHC es más inteligente que el compilador promedio; Si compila con optimizaciones, corregirá el código y lo hará funcionar en un espacio constante.

En términos más generales, hay formas de forzar rigor en puntos específicos en el código Haskell, evitando la construcción de thunks profundamente anidados. Un ejemplo habitual es foldl vs foldl':

len1 = foldl (\x _ -> x + 1) 0 
len2 = foldl' (\x _ -> x + 1) 0 

Ambas funciones son pliegues que hacen el "mismo" que le queda, excepto que foldl es perezosa mientras foldl' es estricta. El resultado es que len1 muere con un desbordamiento de pila en GHCi, mientras que len2 funciona correctamente.