как решить проблему “переполнения пространства стека” в 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
для простоты
Решение
Как ответил пьер, вы должны использовать foldl'
.Для получения более подробной информации:
foldl'
вычисляет его "левую сторону", прежде чем использовать его для вашего шага сгиба.foldr
присваивает вашему шагу сгиба значение "thunk" для правой стороны.Этот "удар" будет рассчитан по мере необходимости.
Давайте составим сумму с помощью 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)?