折り目とモナドアクションを構成します

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

立派以上の慣用的な解決策はありますか？または、おそらく1厳しいですか？ fが重い機能であれば、私はまだ簡単にスタックオーバーフローを取得します。

のUPD：の私は好い加減な形でtimesを書くことはどちらも重いモナドアクションを構成しないという問題を解決していないことがわかりました。これがfのx =ジャスト（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する最初の引数を評価しているという事実に由来しますか？あなたは複雑な構造で作業している場合は、 deepseq のような深いseqを、必要な場合があります。

Answer 3

私はこの思い付います：

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

しかし、それはまた、nの多数のスタックをオーバーフローします。私はそれに見て、今の時間を持っていない以上： - （