4

次のプログラムを実行すると、「スペース オーバーフロー: 現在のサイズ 8388608 バイト」が出力されます。thisとthisを読みましたが、問題の解決方法がわかりません。私は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編集:簡単にするためにの定義を削除します

4

2 に答える 2

11

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': (タグは 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
于 2009-08-18T09:31:08.907 に答える
4

交換

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) の代わりに常に foldl' を使用することをお勧めしますか?

于 2009-08-18T07:27:31.947 に答える