Составление монадных действий со складками

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 является тяжеловесной функцией.

УПД: Я нашел это письмо times в точечной форме не решает и проблему составления тяжеловесных монадических действий.Это работает для f x = Just (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
Just 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, нравиться глубокий секьюрити.

Answer 3

Я придумал это:

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

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