Come funziona la ricorsione della coda di Haskell?

Question

Ho scritto questo frammento di codice e presumo che len sia ricorsivo di coda, ma si verifica ancora un overflow dello stack. Cosa c'è che non va?

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

Ricorda che Haskell è pigro. Il tuo calcolo (l + 1) non avverrà finché non sarà assolutamente necessario.

La correzione 'facile' è usare '$!' per forzare la valutazione:

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

Sembra che la pigrizia induca len a costruire thunk:

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

e così via. Devi forzare len per ridurre l ogni volta:

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

Per ulteriori informazioni, guarda http://haskell.org/haskellwiki/Stack_overflow .

Answer 3

Il foldl presenta lo stesso problema; costruisce un thunk. Puoi usare foldl 'da Data.List per evitare questo problema:

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

L'unica differenza tra foldl e foldl 'è l'accumulo rigoroso, quindi foldl' risolve il problema allo stesso modo di seq e $! esempi sopra. (const.succ) qui funziona come (\ a b - > a + 1), sebbene succ abbia un tipo meno restrittivo.

Answer 4

La soluzione più semplice al tuo problema è attivare l'ottimizzazione.

Ho la tua fonte in un file chiamato 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 I test sopra sono stati eseguiti su Mac OS X Snow Leopard 64 bit con GHC 7 e GHC 6.12.1, ciascuno in una versione a 32 bit. Dopo aver votato, ho ripetuto questo esperimento su Ubuntu Linux con il seguente risultato:

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$ 

Quindi, se sei interessato, possiamo continuare a scoprire qual è la ragione, che ciò non funziona per te. Immagino, GHC HQ, lo accetterebbe come un bug, se in questo caso una ricorsione così semplice sulle liste non fosse ottimizzata in un ciclo efficiente.

Answer 5

Solo per questo sai, c'è un modo molto più semplice di scrivere questa funzione:

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

Alex

Answer 6

eelco.lempsink.nl risponde alla domanda che hai posto. Ecco una dimostrazione della risposta di 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 'scorre l'elenco da sinistra a destra ogni volta aggiungendo 1 ad un accumulatore che inizia da 0.

Ecco un esempio di esecuzione del programma:

---

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>