Haskellで「スタックスペースオーバーフロー」を解決する方法
-
18-09-2019 - |
質問
次のプログラムを実行すると、「スペース オーバーフロー:」と出力されます。現在のサイズは 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
簡単にするために
解決
pierが答えたように、使用する必要があります 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'
:(SO ではタグが適切に表示されないため、コード内でタグが省略されています)
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
他のヒント
置き換え
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のを使用することを好むべきで提案するべきである代わりに、他の変異体(foldlの、foldr)の?
所属していません StackOverflow