Составляющие действия монадов со складками

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 

Есть ли более приятное или более идиоматическое решение? Или, вероятно, более строгий? Я все еще легко получаю переполнение стека, если f - это тяжелая функция.

UPD: Я обнаружил, что написание times в уместной форме не решает проблему составления тяжеловесного монадические действий ни. Это работает для ф х = Just (х + 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 
Just 4000000003

Answer 2

Я пришел с этим:

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

Но это также переполняется стек на большом количестве n. У меня нет времени прямо сейчас, чтобы посмотреть на это более :-(

Answer 3

я бы, вероятно, создать несколько более строгие варианты существующих функций.

{-# 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.