كيفية حل "تكدس مساحة الفضاء" في haskell

Question

تشغيل البرنامج التالي سطباعة "تجاوز الفضاء: الحجم الحالي 8388608 بايت". لقد قرأت هذه و هذه, ، ولكن لا يزال لا يعرف كيفية حل مشكلتي. أنا أستخدم fitrr، ألا ينبغي أن تكون مضمونة لتكون "الذيل العريض"؟

أشعر أنني رائع عن 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

كما أجاب بيير، يجب عليك استخدام foldl'. وبعد لمزيد من التفاصيل:

• foldl' يحسب "الجانب الأيسر" قبل إعطائها خطوة أضعاف.
• foldr يعطي خطوة أضعاف الخاص بك "thunk" لقيمة الجانب الأيمن. سيتم احتساب هذا "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': (تم حذف العلامة في التعليمات البرمجية لأنها لا تعرضها بشكل جيد)

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 أو FILDR)؟