Haskell에서 "스택 공간 오버플로"를 해결하는 방법

Question

다음 프로그램을 실행하면 "공간 오버플로 : 현재 크기 8388608 바이트"가 인쇄됩니다. 내가 읽고 이것 그리고 이것, 그러나 여전히 내 문제를 해결하는 방법을 모릅니다. 나는 foldr를 사용하고있다. "꼬리 재귀"임을 보장해서는 안됩니까?

강력한 재귀를 사용할 때 "공간 오버플로"를 막아야한다는 것을 알 때까지 지금까지 Haskell에 대해 기분이 좋습니다. :)

module Main where
import Data.List

value a  b = 
  let l = length $ takeWhile (isPrime) $ map (\n->n^2 + a * n + b) [0..]
  in (l, a ,b)

euler27 = let tuple_list = [value a b | a <-[-999..999] , b <- [-999..999]]
      in foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list
main = print euler27

편집 : 정의를 제거하십시오 isPrime 단순성을 위해

Answer 1

Pierr가 대답하면 사용해야합니다 foldl'. 자세한 사항은:

• foldl' 접기 단계에주기 전에 "왼쪽"을 계산합니다.
• foldr 오른쪽 값을 위해 접는 단계에 "덩어리"를 제공합니다. 이 "펑크"는 필요할 때 계산됩니다.

합시다 foldr 그리고 그것이 어떻게 평가되는지보십시오 :

foldr (+) 0 [1..3]
1 + foldr (+) 0 [2..3]
1 + 2 + foldr (+) 0 [3]
1 + 2 + 3 + foldl (+) 0 [] -- this is a big thunk..
1 + 2 + 3 + 0
1 + 2 + 3
1 + 5
6

그리고 함께 foldl': (코드에서 태그가 생략됨에 따라 잘 표시되지 않기 때문에)

foldl (+) 0 [1..3]
-- seq is a "strictness hint".
-- here it means that x is calculated before the foldl
x `seq` foldl (+) x [2..3] where x = 0+1
foldl (+) 1 [2..3]
x `seq` foldl (+) x [3] where x = 1+2
foldl (+) 3 [3]
x `seq` foldl (+) x [] where x = 3+3
foldl (+) 6 []
6

좋은 용도로 foldr, 누출되지 않습니다. "단계"는 다음 중 하나입니다.

• "오른쪽"에 의존하지 않는 결과를 반환하거나, 그것을 무시하거나 게으른 구조에 포함 시키십시오.
• 오른쪽을 그대로 반환하십시오

선의 예 foldr 용법:

-- in map, the step returns the structure head
-- without evaluating the "right-side"
map f = foldr ((:) . f) []

filter f =
  foldr step []
  where
    step x rest
      | f x = x : rest -- returns structure head
      | otherwise = rest -- returns right-side as is

any f =
  foldr step False
  where
    -- can use "step x rest = f x || rest". it is the same.
    -- version below used for verbosity
    step x rest
      | f x = True -- ignore right-side
      | otherwise = rest -- returns right-side as is

Answer 2

바꾸다

foldr (\(n,a,b) (max,v) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

~와 함께

foldl' (\(max ,v) (n,a,b) -> if n > max then (n , a * b) else (max ,v) ) (0,0) tuple_list

이 문제를 해결했는데, 우리가 항상 다른 변형 (foldl, foldr) 대신 폴드를 사용하는 것을 선호해야합니까?