haskell - 使用折叠组合 monad Action

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也不能解决组合重量级单子(monad) Action 的问题。这对于 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 3Just 4000000003