Haskell의 게으름과 꼬리 재귀, 왜 충돌이 발생합니까?

StackOverflow https://stackoverflow.com/questions/1618838

문제

지금까지의 합계와 개수를 저장하는 두 개의 누산기를 사용하여 큰 목록 요소의 평균을 계산하는 매우 간단한 함수가 있습니다.

mean = go 0 0
    where
      go s l []     = s / fromIntegral l
      go s l (x:xs) = go (s+x) (l+1) xs

main = do
  putStrLn (show (mean [0..10000000]))

이제 엄격한 언어에서는 이는 꼬리 재귀적이므로 문제가 없습니다.그러나 Haskell은 게으르기 때문에 인터넷 검색을 통해 (s+x)와 (l+1)이 재귀에서 썽크로 전달된다는 것을 알게 되었습니다.그래서 이 모든 것이 충돌하고 화상을 입습니다.

Stack space overflow: current size 8388608 bytes.

좀 더 구글링을 해보니, seq 그리고 $!.이 맥락에서 그것들을 사용하려는 나의 모든 시도는 무한한 유형에 대해 말하는 오류 메시지와 함께 쓸데없는 것으로 판명되었기 때문에 이해하지 못하는 것 같습니다.

마침내 나는 찾았다 -XBangPatterns, 재귀 호출을 변경하여 모든 것을 해결합니다.

go !s !l (x:xs) = go (s+x) (l+1) xs

하지만 나는 이것이 만족스럽지 않습니다. -XBangPatterns 현재 확장 프로그램입니다.를 사용하지 않고 평가를 엄격하게 하는 방법을 알고 싶습니다. -XBangPatterns.(그리고 어쩌면 뭔가를 배울 수도 있습니다!)

저의 이해 부족을 이해해 주실 수 있도록 제가 시도한 방법은 다음과 같습니다(컴파일된 유일한 시도).

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

내가 이해할 수 있는 바에 따르면, seq는 여기서 s 및 l 인수를 강제로 평가하여 썽크로 인한 문제를 피해야 합니다.하지만 여전히 스택 오버플로가 발생합니다.

도움이 되었습니까?

해결책

나는 이것에 대해 광범위하게 썼다 :

첫째, 예, 축적기 사용에 대한 엄격한 평가가 필요하다면 seq Haskell 98에 머물러

mean = go 0 0
  where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = s `seq` l `seq`
                      go (s+x) (l+1) xs

main = print $ mean [0..10000000]

*Main> main
5000000.0

둘째 : 유형 주석을 제공하고 -o2로 컴파일하면 엄격 성 분석이 시작됩니다.

mean :: [Double] -> Double
mean = go 0 0
 where
  go :: Double -> Int -> [Double] -> Double
  go s l []     = s / fromIntegral l
  go s l (x:xs) = go (s+x) (l+1) xs

main = print $ mean [0..10000000]

$ ghc -O2 --make A.hs
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.0
./A  0.46s user 0.01s system 99% cpu 0.470 total

'Double'은 최적화가 켜진 엄격한 원자 유형 Double#의 래퍼이기 때문에 GHC는 엄격한 분석을 실행하고 엄격한 버전이 괜찮을 것이라고 연락합니다.

import Data.Array.Vector

main = print (mean (enumFromToFracU 1 10000000))

data Pair = Pair !Int !Double

mean :: UArr Double -> Double   
mean xs = s / fromIntegral n
  where
    Pair n s       = foldlU k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.5
./A  0.03s user 0.00s system 96% cpu 0.038 total

위의 RWH 장에 설명 된대로.

다른 팁

그만큼 seq 기능이 호출되면 첫 번째 매개 변수의 기능을 강제로 평가합니다. 당신이 지나갈 때 seq s (s+x) 매개 변수로 seq 기능은 ~ 아니다 해당 매개 변수의 값을 평가할 필요가 없기 때문에 즉시 호출됩니다. 당신은 전화를 원합니다 seq 재귀 호출 전에 평가해야하므로 매개 변수를 평가할 수 있습니다.

일반적으로 이것은 이루어집니다. 링크 :

 go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs

이것은 구문 변화입니다 seq s (seq l (go (s+x) (l+1) xs)). 여기에 전화 seq 표현식에서 가장 외부 함수 호출입니다. Haskell의 게으름 때문에 먼저 평가됩니다. seq 아직 평가되지 않은 매개 변수로 호출됩니다 s 그리고 seq l (go (s+x) (l+1) xs), 매개 변수를 평가하는 것은 누군가가 실제로 자신의 값에 액세스하려고하는 지점으로 연기됩니다.

지금 seq 표현식의 나머지 부분을 반환하기 전에 첫 번째 매개 변수를 평가할 수 있습니다. 그러면 평가의 다음 단계는 두 번째 단계입니다. seq. 전화를 한 경우 seq 일부 매개 변수의 어딘가에 묻혀 오랫동안 실행되지 않을 수 있으며 목적을 물리칩니다.

변경된 위치와 함께 seqS 프로그램은 과도한 양의 메모리를 사용하지 않고 잘 실행됩니다.

문제에 대한 또 다른 솔루션은 프로그램이 컴파일 될 때 GHC에서 최적화를 단순히 활성화하는 것입니다 (-O 또는 -O2). Optimizer는 분배 가능한 게으름을 인식하고 불필요한 메모리를 할당하지 않는 코드를 생성합니다.

당신이 이해한 것이 옳습니다. seq s (s+x) 평가를 강요한다 s.하지만 강요하지는 않는다 s+x, 그러므로 당신은 여전히 ​​썽크를 쌓고 있습니다.

사용하여 $! 덧셈을 강제로 평가할 수 있습니다(두 인수 모두에 대해 두 번).이는 강타 패턴을 사용하는 것과 동일한 효과를 얻습니다.

mean = go 0 0
 where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = ((go $! s+x) $! l+1) xs

의 사용 $! 함수는 go $! (s+x) 다음과 같습니다.

let y = s+x 
in seq y (go y)

따라서 y 처음에는 강제로 약한 머리 정상 형태, 이는 가장 바깥쪽의 함수가 적용된다는 의미입니다.의 경우 y, 가장 바깥쪽 함수는 다음과 같습니다. +, 따라서 y 전달되기 전에 숫자로 완전히 평가됩니다. go.

아, 그리고 올바른 위치에 괄호가 없었기 때문에 무한 유형 오류 메시지를 받았을 수도 있습니다.처음 프로그램을 작성할 때 동일한 오류가 발생했습니다 :-)

왜냐하면 $! 연산자는 괄호 없이 오른쪽 연관 연산자입니다. go $! (s+x) $! (l+1) 다음과 같은 의미입니다: go $! ((s+x) $! (l+1)), 이는 분명히 잘못된 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top