使用折叠组合 monad 动作
让我们采用 (Monad m) => 类型的函数一个-> 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
实际上，有效的是使用 ($!)< /code> 严格运算符
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也不能解决组合重量级单子动作的问题。这适用于 fx = Just (x+1) 但在现实世界中失败：
times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)
Let's take a function of type (Monad m) => a -> m a. For example:
ghci> let f x = Just (x+1)
I'd like to be able to apply it any number of times. The first thing I tried was
ghci> let times n f = foldr (>=>) return $ replicate n f
The problem is that it won't work for large n:
ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow
It doesn't work also the other way:
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
Actually, what works is using ($!) strictness operator
ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001
Is there a nicer or more idiomatic solution? Or probably a stricter one? I still easily get stack overflows if f is a heavy-weight function.
UPD: I found that writing times in a pointful form does not solve the problem of composing heavy-weight monadic actions neither. This works for f x = Just (x+1) but fails in the real world:
times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您将
f设置为像or
一样严格，而保留其余部分，则即使
n非常大，您的代码也会在恒定空间中运行（尽管速度很慢）：If you make
fstrict as inor
and leave the rest alone, your code runs in constant space (albeit slowly) even with very large
n:我可能会创建一些现有函数的更严格的变体。
也许您的问题源于
seq仅计算 WHNF 的第一个参数这一事实？如果您正在处理复杂的结构，则可能需要更深的seq，例如 深度序列。I'd probably create some stricter variants of existing functions.
Perhaps your problems stem from the fact that
seqonly evaluates the first argument to WHNF? If you're working on a complex structure, you may need a deeperseq, like deepseq.我想出了这个：
但它也会在大量
n上溢出堆栈。我现在没有时间进一步研究:-(I came up with this:
But it also overflows the stack on large numbers of
n. I don't have the time right now to look into it more :-(