折叠这是恒定空间和短路

Question

我正在尝试构建一个与Prelude的product完全相同的Haskell函数。但是，与该函数不同，它应该具有以下两个属性：

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

这完全符合我对列表的要求，但我想将其概括为(Foldable t, Eq n, Num n) => t n -> n类型。是否可以使用任何折叠进行此操作？如果我只使用foldr，那么它将短路但不会是恒定空间，如果我只使用foldl'，那么它将是恒定空间但不会短路。

Answer 1

你可能正在寻找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

Answer 2

如果你的功能略有不同，那么如何将它变成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上短路，并使用恒定的空间。