как решить «переполнение стека» в haskell

Question

Запуск следующей программы приведет к печати «переполнение пространства: текущий размер 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 

EDIT: удалить Definiton из 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': (тэг опущен в коде, потому что 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 

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 'вместо других вариантов (foldl, foldr)?