¿Cómo funciona la recursividad de Haskell tail?

Question

Escribí este fragmento de código y supongo que len es recursivo de cola, pero aún se produce un desbordamiento de la pila. ¿Qué está mal?

myLength :: [a] -> Integer 

myLength xs = len xs 0 
    where len [] l = l 
      len (x:xs) l = len xs (l+1) 

main = print $ myLength [1..10000000] 

Answer 1

Recuerda que Haskell es flojo. Su cálculo (l + 1) no ocurrirá hasta que sea absolutamente necesario.

La solución 'fácil' es usar '$!' para forzar la evaluación:

myLength :: [a] -> Integer 
myLength xs = len xs 0 
where len [] l = l 
     len (x:xs) l = len xs $! (l+1) 

     main = print $ myLength [1..10000000] 

Answer 2

parece que la pereza hace que len para construir golpe seco:

len [1..100000] 0 
-> len [2..100000] (0+1) 
-> len [3..100000] (0+1+1) 

y así sucesivamente. Debe forzar len para reducir l cada vez que:

len (x:xs) l = l `seq` len xs (l+1) 

Para obtener más información, busque http://haskell.org/haskellwiki/Stack_overflow.

Answer 3

Para que lo sepas, hay una manera mucho más fácil escribir esta función:

myLength xs = foldl step 0 xs where step acc x = acc + 1

Alex

Answer 4

El foldl lleva el mismo problema; construye un thunk. Puede utilizar foldl 'de Data.List para evitar ese problema:

import Data.List 
myLength = foldl' (const.succ) 0 

La única diferencia entre foldl y foldl' es la acumulación estricta, por lo foldl' resuelve el problema de la misma manera que la SEC y $! ejemplos arriba. (const.succ) aquí funciona igual que (\ a b -> a + 1), aunque succ tiene un tipo menos restrictivo.

Answer 5

eelco.lempsink.nl responde a la pregunta que ha planteado. He aquí una demostración de la respuesta de Yann:

module Main 
    where 

import Data.List 
import System.Environment (getArgs) 

main = do 
    n <- getArgs >>= readIO.head 
    putStrLn $ "Length of an array from 1 to " ++ show n 
       ++ ": " ++ show (myLength [1..n]) 

myLength :: [a] -> Int 
myLength = foldl' (const . succ) 0 

foldl' pasa a través de la lista de izquierda a derecha cada vez añadiendo 1 a un acumulador que comienza en 0.

He aquí un ejemplo de cómo ejecutar el programa:

---

C:\haskell>ghc --make Test.hs -O2 -fforce-recomp 
[1 of 1] Compiling Main    (Test.hs, Test.o) 
Linking Test.exe ... 

C:\haskell>Test.exe 10000000 +RTS -sstderr 
Test.exe 10000000 +RTS -sstderr 

Length of an array from 1 to 10000000: 10000000 
    401,572,536 bytes allocated in the heap 
      18,048 bytes copied during GC 
      2,352 bytes maximum residency (1 sample(s)) 
      13,764 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 765 collections,  0 parallel, 0.00s, 0.00s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 0.27s ( 0.28s elapsed) 
    GC time 0.00s ( 0.00s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 0.27s ( 0.28s elapsed) 

    %GC time  0.0% (0.7% elapsed) 

    Alloc rate 1,514,219,539 bytes per MUT second 

    Productivity 100.0% of total user, 93.7% of total elapsed 


C:\haskell> 

Answer 6

La solución más sencilla a su problema se está convirtiendo en la optimización.

Tengo su fuente en un archivo llamado tail.hs.

 
jmg$ ghc --make tail.hs -fforce-recomp 
[1 of 1] Compiling Main    (tail.hs, tail.o) 
Linking tail ... 
jmg$ ./tail 
Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 
girard:haskell jmg$ ghc -O --make tail.hs -fforce-recomp 
[1 of 1] Compiling Main    (tail.hs, tail.o) 
Linking tail ... 
jmg$ ./tail 
10000000 
jmg$ 

@Hynek -Pichi- Vychodil los ensayos anteriores se realizaron en Mac OS X Snow Leopard de 64 bits con un GHC 7 y GHC 6.12.1, cada uno en una versión de 32 bit. Después de que esté downvote, repetí este experimento en Ubuntu Linux con el siguiente resultado:

 
jmg@girard:/tmp$ cat length.hs 
myLength :: [a] -> Integer 

myLength xs = len xs 0 
    where len [] l = l 
      len (x:xs) l = len xs (l+1) 

main = print $ myLength [1..10000000] 

jmg@girard:/tmp$ ghc --version 
The Glorious Glasgow Haskell Compilation System, version 6.12.1 
jmg@girard:/tmp$ uname -a 
Linux girard 2.6.35-24-generiC#42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux 
jmg@girard:/tmp$ ghc --make length.hs -fforce-recomp 
[1 of 1] Compiling Main    (length.hs, length.o) 
Linking length ... 
jmg@girard:/tmp$ time ./length 
Stack space overflow: current size 8388608 bytes. 
Use `+RTS -Ksize -RTS' to increase it. 

real 0m1.359s 
user 0m1.140s 
sys 0m0.210s 
jmg@girard:/tmp$ ghc -O --make length.hs -fforce-recomp 
[1 of 1] Compiling Main    (length.hs, length.o) 
Linking length ... 
jmg@girard:/tmp$ time ./length 
10000000 

real 0m0.268s 
user 0m0.260s 
sys 0m0.000s 
jmg@girard:/tmp$ 

lo tanto, si usted está interesado podemos continuar para averiguar cuál es la razón, que esto no funciona para usted. Supongo que GHC HQ lo aceptaría como un error, si una recursión tan directa sobre las listas no se optimiza en un ciclo eficiente en este caso.