تأليف إجراءات مناد مع طيات

Question

دعونا نأخذ وظيفة من النوع (Monad m) => a -> m a. وبعد علي سبيل المثال:

ghci> let f x = Just (x+1)

أود أن أكون قادرا على تطبيقه أي عدد من المرات. أول شيء حاولت

ghci> let times n f = foldr (>=>) return $ replicate n f

المشكلة هي أنه لن يعمل كبير n:

ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow

لا يعمل أيضا على عكس ذلك:

ghci> let timesl n f = foldl' (<=<) return $ replicate n f
ghci> 3 `timesl` f $ 1
Just 4
ghci> 1000000 `timesl` f $ 1
Just *** Exception: stack overflow

في الواقع، ما يعمل يستخدم ($!) مشغل صارمة

ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001

هل هناك حل أجمل أو أكثر oriomatic؟ أو ربما أكثر صرامة؟ ما زلت بسهولة الحصول على تفيضات المكدس إذا f هي وظيفة ثقيلة الوزن.

تحديث لقد وجدت أن الكتابة times في شكل منشور لا يحل مشكلة إنشاء تصرفات الأوناديك الثقيلة لا. هذا يعمل fx = فقط (x + 1) ولكنه فشل في العالم الحقيقي:

times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)

Answer 1

إذا قمت بإجراء f صارمة كما في

f x = let y = x+1 in y `seq` Just y

أو

-- remember to enable -XBangPatterns
f !x = Just (x+1)

وترك البقية بمفردها، يدير الكود الخاص بك في مساحة ثابتة (وإن كانت ببطء) حتى مع كبير جدا n:

GHCI> Times 4000000000 F 3 فقط 4000000003

Answer 2

من المحتمل أن أقوم بإنشاء بعض المتغيرات الأكثر صرامة للوظائف الموجودة.

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate' f (f x)
ma >>=! f = do !a <- ma; f a
times' n f a = iterate' (>>=! f) (return a) !! n

ربما مشاكلك تنبع من حقيقة أن seq فقط تقييم الحجة الأولى إلى WHNF؟ إذا كنت تعمل على هيكل معقد، فقد تحتاج إلى أعمق seq, ، مثل deepseq..

Answer 3

خطرت لي هذه:

 last $ take n $ iterate (>>= f) $ Just 1

لكنه يفيض أيضا المكدس على أعداد كبيرة من n. وبعد ليس لدي الوقت الآن للنظر في ذلك أكثر :-(