Haskell Tail Recursion은 어떻게 작동합니까?
https://stackoverflow.com/questions/412919
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는이 코드 스 니펫을 썼고 나는 가정한다 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]
해결책
Haskell은 게으르다는 것을 기억하십시오. 귀하의 계산 (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]
다른 팁
게으름 원인처럼 보입니다 len Thunk를 구축하려면 :
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.
Foldl은 동일한 문제를 가져옵니다. 그것은 덩어리를 만듭니다. Data.list의 Foldl '를 사용하여 해당 문제를 피할 수 있습니다.
import Data.List
myLength = foldl' (const.succ) 0
Foldl과 Foldl '의 유일한 차이점은 엄격한 축적이므로 Foldl'은 seq 및 $와 같은 방식으로 문제를 해결합니다! 위의 예. (const.succ) 여기에서는 ( ab-> a+1)과 동일하지만 Succ는 덜 제한적인 유형을 가지고 있습니다.
문제에 대한 가장 간단한 해결책은 최적화를 켜는 것입니다.
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 위의 테스트는 각각 32 비트 버전으로 GHC 7 및 GHC 6.12.1을 갖춘 Mac OS X Snow Leopard 64 비트에서 수행되었습니다. 다운 투표 후, 나는 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 본사는이 경우 에도이 간격의 재귀가 효율적인 루프로 최적화되지 않으면 버그로 받아 들일 것이라고 생각합니다.
알다시피,이 기능을 작성하는 훨씬 쉬운 방법이 있습니다.
myLength xs = foldl step 0 xs where step acc x = acc + 1
알렉스
eelco.lempsink.nl은 질문에 답변합니다. 다음은 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 '은 매번 왼쪽에서 오른쪽으로 목록을 통과하여 1을 0에서 시작하는 축적기에 1을 추가합니다.
다음은 프로그램을 실행하는 예입니다.
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>
