Как работает хвостовая рекурсия на Haskell?

Question

Я написал этот фрагмент кода, и я предполагаю, что len является хвост-рекурсивным, но переполнение стека все еще происходит. Что не так?

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

Помните, что Хаскелл ленив. Ваше вычисление (l + 1) не произойдет, пока это не станет абсолютно необходимым.

Простое исправление заключается в использовании $! форсировать оценку:

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

Похоже, из-за лени len создает гром:

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

и так далее. Вы должны заставить len уменьшать l каждый раз:

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

Для получения дополнительной информации смотрите http://haskell.org/haskellwiki/Stack_overflow.

Answer 3

Складка несет ту же проблему; это строит гром. Вы можете использовать foldl 'из Data.List, чтобы избежать этой проблемы:

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

Единственная разница между foldl и foldl 'заключается в строгом накоплении, поэтому foldl' решает проблему так же, как seq и $! примеры выше. (const.succ) здесь работает так же, как (\ a b -> a + 1), хотя succ имеет менее ограничительный тип.

Answer 4

Самое простое решение вашей проблемы - включение оптимизации.

У меня есть ваш источник в файле с именем 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 Вышеприведенные тесты проводились на Mac OS X Snow Leopard 64bit с GHC 7 и GHC 6.12.1, каждый в 32-битной версии. После того, как вы понизили голос, я повторил этот эксперимент на Ubuntu Linux со следующим результатом:

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$ 

Итак, если вам интересно, мы можем продолжить выяснять, в чем причина, что это не сработало для вас. Я думаю, штаб-квартира GHC приняла бы это как ошибку, если бы в этом случае такая прямая рекурсия по спискам не была оптимизирована в эффективный цикл.

Answer 5

eelco.lempsink.nl отвечает на заданный вами вопрос. Вот демонстрация ответа Янна:

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 'просматривает список слева направо каждый раз, добавляя 1 к аккумулятору, который начинается с 0.

Вот пример запуска программы:

---

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

Как вы знаете, есть гораздо более простой способ написать эту функцию:

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

Alex