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

funciones recursivas ejemplos

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

El pliegue lleva el mismo problema; 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 el seq y $! ejemplos arriba. (const.succ) aquí funciona igual que (/ ab -> a + 1), aunque succ tiene un tipo menos restrictivo.

Answer 2

La solución más simple para su problema es activar la optimización.

Tengo tu 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 de 64 bits con un GHC 7 y GHC 6.12.1, cada uno en una versión de 32 bits. Después de declinar, 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 averiguando cuál es el motivo, 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.

Answer 3

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

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

Alex

Answer 4

Parece que la pereza hace que Len cree un thunk:

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

y así. Debes forzar a len a reducir l cada vez:

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

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

Answer 5

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

La solución ''fácil'' es usar ''$!'' 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 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 ''pasa por la lista de izquierda a derecha cada vez que agrega 1 a un acumulador que comienza en 0.

Aquí hay un ejemplo de 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>