折叠常数-space和短路

Question

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

它应该以常量 space 运行（忽略一些数字类型如 Integer 不是的事实）。例如，我希望 myProduct (replicate 100000000 1) 最终成为 return 1，这与 Prelude 的 product 不同，它用完了我所有的 RAM，然后给出 *** Exception: stack overflow.
遇到0应该短路，比如我要myProduct (0:undefined)到return0，不像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，那么它会短路，但不会是常量-space，如果我只用foldl'，它就会常量-space ] 但不会短路

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 上短路，并在专门用于列表时使用常量 space。

折叠常数-space和短路

Fold that's both constant-space and short-circuiting

haskell

fold

short-circuiting

space-complexity