Haskell 有 FoldlM' 吗？

发布于 2024-12-27 12:59:16 字数 683 浏览 1 评论 0原文

如何严格折叠 monad？ Data.Foldable 有严格的 foldl' 和单子 foldlM，但没有严格的 foldlM'？严格性是由单子本身以某种方式定义的吗？如果是这样，如何弄清楚它是什么？

想象一下，我必须确定大量环元素的乘积是否为零，但我的环不是积分域，即它包含零除数。在这种情况下，我应该在列表上递归foldl我的乘法***，但在乘积变为零时返回False，而不是而不是等待完整的产品。

safelist :: [p] -> Bool
safelist [] = True
safelist (x:xs) = snd $ foldl' f (x,True) xs
   where  f (u,b) v = (w, b && w /= Zero)  where  w = u *** v

我也许可以使用 Maybe monad 的 foldlM 稍微简化此代码，但这样做似乎缺乏所需的严格性。

原文

How does one fold over a monad strictly? Data.Foldable has the strict foldl' and the monadic foldlM, but no strict foldlM'? Is the strictness somehow defined by the monad itself? If so, how does one work out what it is?

Imagine I must determine whether the product of an enormous list of ring elements is zero, but my ring isn't an integral domain, i.e. it contains zero devisors. In this case, I should tail recursively foldl my multiplication *** over the list, but return False the moment the product becomes zero, rather than waiting on the full product.

safelist :: [p] -> Bool
safelist [] = True
safelist (x:xs) = snd $ foldl' f (x,True) xs
   where  f (u,b) v = (w, b && w /= Zero)  where  w = u *** v

I could perhaps simplify this code slightly using the Maybe monad's foldlM but doing so seemingly lacks the required strictness.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

§普罗旺斯的薰衣草 2025-01-03 12:59:16

没有这样的标准函数，但很容易定义：

foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
  z' <- f z x
  z' `seq` foldM' f z' xs

这只是标准的 foldM，但其中具有与 foldl' 相同的 seqing > 确实如此（与 foldl 相比）。它可能没有在任何标准中定义，因为它不太可能那么有用：对于大多数单子， (>>=) 是“严格的”，因为您需要使用左折叠而不需要使用左折叠堆栈溢出；仅当返回值本身包含过多的 thunk 时，这才有用，但是 foldM 的有用应用程序将使用上一步的值执行一些单子计算，从而使这种情况不太可能发生。

我认为你的代码很简单；我怀疑 foldM' 会让它变得更加优雅。

There's no such standard function, but it's easy to define:

foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
  z' <- f z x
  z' `seq` foldM' f z' xs

This is just the standard foldM, but with the same seqing in it that foldl' does (compared to foldl). It's probably not defined anywhere standard because it's not likely to be all that useful: for most monads, (>>=) is "strict" in the sense you need to use a left-fold without overflowing the stack; this is only useful when your excessive thunks are in the returned values themselves, but a useful application of foldM will perform some monadic computation with the value from the last step, making that unlikely.

I think your code is simple enough as it is; I doubt foldM' would make it any more elegant.

回复收藏 0 原文

~没有更多了~