¿Cómo funciona la recursividad de cola de Haskell?

Question

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

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 perezoso. 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 genere thunk:

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

y así sucesivamente. Debe obligar a len a reducir l cada vez que:

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

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

Answer 3

El foldl conlleva el mismo problema; se construye un thunk. Puede usar 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, ¡así que foldl' resuelve el problema de la misma manera que seq y $! ejemplos anteriores (const.succ) aquí funciona igual que (\ a b - > a + 1), aunque succ tiene un tipo menos restrictivo.

Answer 4

La solución más sencilla para su problema es activar 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 Las pruebas anteriores se realizaron en Mac OS X Snow Leopard 64bit con un GHC 7 y GHC 6.12.1, cada uno en una versión de 32 bits. Después de que estás a la baja, 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$ 

Entonces, si está interesado, podemos continuar descubriendo cuál es la razón, que esto falla 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 bucle eficiente en este caso.

Answer 5

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

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

Alex

Answer 6

eelco.lempsink.nl responde la pregunta que hizo. Aquí hay 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 'recorre la lista de izquierda a derecha cada vez que agrega 1 a un acumulador que comienza en 0.

Aquí hay un ejemplo de ejecución del 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>