متغير مثلث باسكال في هاسكل - مشكلة مع التقييم البطيئة

Question

لحل بعض المشكلات ، أحتاج إلى حساب متغير من مثلث Pascal الذي يتم تعريفه على النحو التالي:

f(1,1) = 1, 
f(n,k) = f(n-1,k-1) + f(n-1,k) + 1 for 1 <= k < n, 
f(n,0) = 0,
f(n,n) = 2*f(n-1,n-1) + 1.

بالنسبة إلى n ، أريد أن أحصل على خط N-Th بكفاءة (F (n ، 1) .. f (n ، n)). أحد القيود الأخرى: يجب أن يكون F (n ، k) -1 إذا كان ذلك> = 2^32.

تنفيذي:

next :: [Int64] -> [Int64]
next list@(x:_) = x+1 : takeWhile (/= -1) (nextRec list)

nextRec (a:rest@(b:_)) = boundAdd a b : nextRec rest
nextRec [a] = [boundAdd a a]

boundAdd x y
    | x < 0 || y < 0 = -1
    | x + y + 1 >= limit = -1
    | otherwise = (x+y+1)

-- start shoud be [1]
fLine d start = until ((== d) . head) next start

المشكلة: بالنسبة للأعداد الكبيرة جدًا ، أحصل على فائض مكدس. هل هناك طريقة لإجبار هاسكل على تقييم القائمة بأكملها؟ من الواضح أن كل سطر لا يمكن أن يحتوي على عناصر أكثر من الحد الأعلى ، لأنها تصبح في النهاية -1 ولا يتم تخزينها ويعتمد كل سطر فقط على السابقين. نظرًا للتقييم البطيء ، يتم حساب رأس كل سطر فقط حتى يحتاج السطر الأخير إلى العنصر الثاني ويتم تخزين جميع جذوعها على طول الطريق ... لدي تطبيق فعال للغاية في C ++ لكنني أتساءل حقًا عما إذا كان هناك أ طريقة لإنجازها في هاسكل أيضًا.

Answer 1

تناسبني: ما هو تطبيق Haskell الذي تستخدمه؟ برنامج ساذج لحساب هذا المثلث يعمل بشكل جيد بالنسبة لي في GHC 6.10.4. يمكنني طباعة الصف الأول على ما يرام:

nextRow :: [Integer] -> [Integer]
nextRow row = 0 : [a + b + 1 | (a, b) <- zip row (tail row ++ [last row])]

tri = iterate nextRow [0]

main = putStrLn $ show $ tri !! 1000               -- print 1000th row

يمكنني حتى طباعة الأرقام العشرة الأولى في الصف 100000 دون فائض المكدس. لست متأكدًا من الخطأ الذي يحدث لك. الاسم العالمي tri قد يكون الحفاظ على المثلث الكامل للنتائج حية ، ولكن حتى لو كان ذلك ، يبدو ذلك غير ضار نسبيًا.

كيفية فرض ترتيب التقييم: يمكنك إجبار Thunks على تقييمها في ترتيب معين باستخدام وظيفة Prelude seq (وهي وظيفة سحرية لا يمكن تنفيذها من حيث الميزات الأساسية الأخرى لـ Haskell). إذا أخبرت Haskell الطباعة a `seq` b, ، يقوم أولاً بتقييم thunk a, ثم يقيم ويطبع b.

لاحظ أن seq ضحل: هو فقط قم بتقييم كافٍ للقوة a لم يعد يكون ثونك. لو a من نوع tuple ، قد لا تزال النتيجة عبارة عن tuple من thunks. إذا كانت قائمة ، فقد تكون النتيجة خلية سلبية لها ثونكس لكل من الرأس والذيل.

يبدو أنك لا تحتاج إلى القيام بذلك لمثل هذه المشكلة البسيطة ؛ لا ينبغي أن يكون بضعة آلاف من Thunks أكثر من اللازم لأي تطبيق معقول. لكنه سيحدث مثل هذا:

-- Evaluate a whole list of thunks before calculating `result`.
-- This returns `result`.
seqList :: [b] -> a -> a
seqList lst result = foldr seq result lst

-- Exactly the same as `nextRow`, but compute every element of `row`
-- before calculating any element of the next row.
nextRow' :: [Integer] -> [Integer]
nextRow' row = row `seqList` nextRow row

tri = iterate nextRow' [0]

أضعاف في seqList يتوسع أساسا إلى lst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` result.

هذا أبطأ بكثير بالنسبة لي عند طباعة العناصر العشرة الأولى من الصف 100000. أعتقد أن هذا يتطلب حساب 99،999 صفوف كاملة من المثلث.