折叠既是恒定空间又是短路

Question

我正在尝试构建一个 Haskell 函数，它与 Prelude 的product. 然而，与该函数不同的是，它应该具有以下两个属性：

1. 它应该在常量空间中运行（忽略某些数字类型Integer不是这样的事实）。例如，我想myProduct (replicate 100000000 1)最终返回 1，与 Prelude 不同product，它用完我所有的 RAM 然后给出*** Exception: stack overflow.
2. 它应该在遇到 0 时短路。例如，我想myProduct (0:undefined)返回 0，与 Prelude 的不同product，它给出*** Exception: Prelude.undefined.

到目前为止，这是我想出的：

myProduct :: (Eq n, Num n) => [n] -> n
myProduct = go 1
  where go acc (x:xs) = if x == 0 then 0 else acc `seq` go (acc * x) xs
        go acc []     = acc

这正是我希望它用于列表的方式，但我想将其概括为具有 type (Foldable t, Eq n, Num n) => t n -> n。是否可以用任何折叠来做到这一点？如果我只使用foldr，那么它会短路但不会是常数空间，如果我只使用foldl'，那么它将是常数空间但不会短路。

Answer 1

如果您的函数拼写稍有不同，那么如何将其转换为foldr. 即：

myProduct :: (Eq n, Num n) => [n] -> n
myProduct = flip go 1 where
    go (x:xs) = if x == 0 then \acc -> 0 else \acc -> acc `seq` go xs (acc * x)
    go [] = \acc -> acc

现在go已经有了那种foldr味道，我们可以填补漏洞了。

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct = flip go 1 where
    go = foldr
        (\x f -> if x == 0 then \acc -> 0 else \acc -> acc `seq` f (acc * x))
        (\acc -> acc)

希望您能看到这些部分在以前的显式递归风格中来自哪里以及转换是多么机械。然后我会做一些美学调整：

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct xs = foldr step id xs 1 where
    step 0 f acc = 0
    step x f acc = f $! acc * x

我们都完成了！在 ghci 中进行的一些快速测试表明，它仍然根据0需要短路，并且在专门用于列表时使用恒定空间。

Answer 2

您可能正在寻找foldM. 用 实例化它m = Either b，您会得到短路行为（或者Maybe，取决于您是否有许多可能的早期退出值，或者提前已知的值）。

foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

我记得讨论过是否应该有foldM'，但 IIRC GHC 大多数时候都做了正确的事情。

import Control.Monad
import Data.Maybe

myProduct :: (Foldable t, Eq n, Num n) => t n -> n
myProduct = fromMaybe 0 . foldM go 1
  where go acc x = if x == 0 then Nothing else Just $! acc * x