الكسل والتكرار في هاسكل، لماذا هذا الانهيار؟

Question

لدي هذه الوظيفة البسيطة إلى حد ما لحساب متوسط ​​عناصر القائمة الكبيرة، وذلك باستخدام مجمعين للاحتفاظ بالمجموع حتى الآن والعدد حتى الآن:

mean = go 0 0
    where
      go s l []     = s / fromIntegral l
      go s l (x:xs) = go (s+x) (l+1) xs

main = do
  putStrLn (show (mean [0..10000000]))

الآن، بلغة صارمة، سيكون هذا تكراريًا، ولن تكون هناك مشكلة.ومع ذلك، نظرًا لأن هاسكل كسول، فقد قادني البحث على Google إلى فهم أن (s+x) و(l+1) سيتم تمريرهما إلى أسفل العودية على هيئة أجزاء.لذلك يتعطل هذا الأمر برمته ويحترق:

Stack space overflow: current size 8388608 bytes.

وبعد مزيد من البحث على جوجل، وجدت seq و $!.والذي يبدو أنني لا أفهمه لأن كل محاولاتي لاستخدامها في هذا السياق أثبتت عدم جدواها، مع وجود رسائل خطأ تقول شيئًا عن الأنواع اللانهائية.

وأخيرا وجدت -XBangPatterns, ، والذي يحل كل شيء عن طريق تغيير المكالمة العودية:

go !s !l (x:xs) = go (s+x) (l+1) xs

لكنني لست سعيدا بهذا، كما -XBangPatterns حاليا امتدادا.أود أن أعرف كيفية جعل التقييم صارمًا دون استخدام -XBangPatterns.(وربما تتعلم شيئًا أيضًا!)

لكي تفهم عدم فهمي، إليك ما جربته (المحاولة الوحيدة التي تم تجميعها هي):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

مما أستطيع أن أفهمه، يجب أن يفرض seq هنا تقييم الوسيطة s وl، وبالتالي تجنب المشكلة التي تسببها thunks.لكن ما زلت أحصل على تجاوز سعة المكدس.

Answer 1

لقد كتبت على نطاق واسع حول هذا:

• العالم الحقيقي هاسكل، الفصل 24:تقييم السيطرة
• على التكرار والصرامة في هاسكل

أولاً، نعم، إذا كنت تريد أن تطلب تقييمًا صارمًا لاستخدام البطاريات seq والبقاء في هاسكل 98:

mean = go 0 0
  where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = s `seq` l `seq`
                      go (s+x) (l+1) xs

main = print $ mean [0..10000000]

*Main> main
5000000.0

ثانيًا:سيتم بدء تحليل الصرامة إذا أعطيت بعض التعليقات التوضيحية للنوع، وقمت بتجميعها باستخدام -O2:

mean :: [Double] -> Double
mean = go 0 0
 where
  go :: Double -> Int -> [Double] -> Double
  go s l []     = s / fromIntegral l
  go s l (x:xs) = go (s+x) (l+1) xs

main = print $ mean [0..10000000]

$ ghc -O2 --make A.hs
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.0
./A  0.46s user 0.01s system 99% cpu 0.470 total

نظرًا لأن "Double" عبارة عن غلاف للنوع الذري الصارم Double#، مع تشغيل التحسينات ونوع دقيق، تجري GHC تحليلًا صارمًا وتستنتج أن الإصدار الصارم سيكون جيدًا.

import Data.Array.Vector

main = print (mean (enumFromToFracU 1 10000000))

data Pair = Pair !Int !Double

mean :: UArr Double -> Double   
mean xs = s / fromIntegral n
  where
    Pair n s       = foldlU k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.5
./A  0.03s user 0.00s system 96% cpu 0.038 total

كما هو موضح في فصل RWH أعلاه.

Answer 2

ال seq تفرض الدالة تقييم المعلمة الأولى بمجرد استدعاء الدالة.عندما تمر seq s (s+x) كمعلمة seq الوظيفة هي لا يتم استدعاؤه على الفور، لأنه ليست هناك حاجة لتقييم قيمة تلك المعلمة.تريد الاتصال به seq ليتم تقييمه قبل الاستدعاء العودي، بحيث يمكن بدوره فرض تقييم المعلمة الخاصة به.

عادة ما يتم ذلك الرابط هذا:

 go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs

هذا هو الاختلاف النحوي ل seq s (seq l (go (s+x) (l+1) xs)).هنا يدعو إلى seq هي استدعاءات الوظائف الخارجية في التعبير.وبسبب كسل هاسكل فإن هذا يؤدي إلى تقييمهم أولاً: seq يتم استدعاؤه باستخدام المعلمات التي لم يتم تقييمها بعد s و seq l (go (s+x) (l+1) xs), ، يتم تأجيل تقييم المعلمات إلى النقطة التي يحاول فيها شخص ما بالفعل الوصول إلى قيمها.

الآن seq يمكن أن يفرض تقييم المعلمة الأولى قبل إرجاع بقية التعبير.ثم الخطوة التالية في التقييم ستكون الثانية seq.إذا كانت المكالمات إلى seq يتم دفنهم في مكان ما في بعض المعلمات وقد لا يتم إعدامهم لفترة طويلة، مما يتعارض مع غرضهم.

ومع تغير مواقف seqيتم تنفيذ البرنامج بشكل جيد، دون استخدام كميات زائدة من الذاكرة.

الحل الآخر للمشكلة هو ببساطة تمكين التحسينات في GHC عند تجميع البرنامج (-O أو -O2).يتعرف المُحسِّن على الكسل الذي يمكن الاستغناء عنه وينتج تعليمات برمجية لا تخصص ذاكرة غير ضرورية.

Answer 3

أنت على حق في فهمك لذلك seq s (s+x) يفرض التقييم s.لكنها لا تجبر s+x, ، وبالتالي فإنك لا تزال تقوم ببناء الأعداد الكبيرة.

باستخدام $! يمكنك فرض تقييم الإضافة (مرتين لكلا الوسيطتين).يحقق هذا نفس تأثير استخدام أنماط الانفجارات:

mean = go 0 0
 where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = ((go $! s+x) $! l+1) xs

---

استخدام $! سوف تقوم الدالة بترجمة go $! (s+x) إلى ما يعادل:

let y = s+x 
in seq y (go y)

هكذا y يُجبر أولاً على رأس ضعيف بالشكل الطبيعي, ، مما يعني أنه تم تطبيق الوظيفة الخارجية.في حالة y, ، الوظيفة الخارجية هي +, ، هكذا y يتم تقييمه بالكامل إلى رقم قبل أن يتم تمريره إليه go.

---

أوه، ومن المحتمل أنك حصلت على رسالة خطأ الكتابة اللانهائية لأنه لم يكن لديك القوس في المكان الصحيح.لقد حصلت على نفس الخطأ عندما كتبت برنامجك لأول مرة :-)

بسبب ال $! المشغل هو النقابي الصحيح، دون قوسين go $! (s+x) $! (l+1) يعني نفس: go $! ((s+x) $! (l+1)), ، وهو خطأ واضح.