Haskell的懒惰是Python生成器的优雅替代品吗？

Question

在编程练习中，首先要求编写阶乘函数，然后计算O(n)乘法中的和：1! + 2! + 3! +... n!（因此我们不能直接使用阶乘）。我不是在寻找这个具体（琐碎）问题的解决方案，而是在探索Haskell的能力，这个问题是我想玩的玩具。在

我认为Python的生成器可以很好地解决这个问题。例如：

from itertools import islice
def ifact():
    i , f = 1, 1
    yield 1
    while True:
        f *= i
        i += 1
        yield f

def sum_fact(n):
    return sum(islice(ifact(),5))

然后我试着弄清楚Haskell是否有什么东西与这个生成器有着相似的行为，我认为懒惰对所有的员工都没有任何额外的概念。在

例如，我们可以用

^{pr2}$

然后用以下方法解决这个练习：

sum n = foldl1 (+) (take n fact)

我想知道这个解决方案在时间复杂性和内存使用方面是否真的“等价”于Python的解决方案。我想说Haskell的解决方案从来没有存储所有的列表事实，因为它们的元素只被使用一次。在

我是对的还是完全错的？在

---

编辑： 我应该更精确地检查一下：

Prelude> foldl1 (+) (take 4 fact)
33
Prelude> :sprint fact
fact = 1 : 2 : 6 : 24 : _

因此（我的实现）Haskell存储结果，即使它不再使用。在

Answer 1

你的例子在内存使用上是不等价的。很容易看出您是否将*替换为+（这样数字就不会太快变大），然后在一个大的n上运行这两个示例，比如10^7。Haskell版本将消耗大量内存，python将保持较低的内存。在

Python生成器不会生成一个值列表，然后对其求和。相反，sum函数将从生成器中逐个获取值并累加。因此，内存使用量将保持不变。在

Haskell将延迟地计算函数，但是为了计算foldl1 (+) (take n fact)，它必须计算完整的表达式。对于大的n，这将展开为一个巨大的表达式，就像(foldl (+) 0 [0..n])一样。有关求值和约简的详细信息，请看这里：https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27。在

您可以通过使用foldl1'而不是上面链接中所述的foldl1来修复{}。正如@user2407038在他的评论中所解释的，您还需要将fact保持在本地。以下内容在GHC中使用恒定内存：

let notfact = scanl1 (+) [1..]
let n = 20000000
let res = foldl' (+) 0 (take n notfact)

注意，在实际阶乘代替notfact的情况下，内存方面的考虑就不那么重要了。数字会很快变大，任意精度的算术运算会减慢速度，因此您无法获得n的大值，以便真正看到差异。在

Answer 2

实际上，惰性列表可以这样使用。但也有一些细微的区别：

• 列表是数据结构。因此，您可以在评估它们之后保留它们，这可能是好的也可能是坏的（您可以避免重新计算值和使用@ChrisDrost所描述的递归技巧，代价是保持内存未释放）。在
• 名单是纯粹的。在生成器中，可以使用副作用进行计算，但不能使用列表（这通常是可取的）。在
• 由于Haskell是一种懒惰语言，懒惰无处不在，如果您只是将一个程序从命令式语言转换为Haskell，那么内存需求可能会发生很大变化（正如@romal在他的回答中所描述的那样）。在

但是Haskell提供了更高级的工具来完成生成器/消费者模式。目前有三个库关注这个问题：pipes, conduit and iteratees。我最喜欢的是conduit，它易于使用，并且其类型的复杂性保持在较低水平。在

它们有几个优点，特别是可以创建复杂的管道，并且可以基于选定的monad，这允许您说出管道中允许的副作用。在

使用导管，您的示例可以表示为：

import Data.Functor.Identity
import Data.Conduit
import qualified Data.Conduit.List as C

ifactC :: (Num a, Monad m) => Producer m a
ifactC = loop 1 1
  where
    loop r n = let r' = r * n
                in yield r' >> loop r' (n + 1)

sumC :: (Num a, Monad m) => Consumer a m a
sumC = C.fold (+) 0

main :: IO ()
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC)
  alternatively running the pipeline in IO monad directly:
  main = (ifactC $= C.isolate 5 $$ sumC) >>= print

这里我们创建一个Producer（一个不消耗输入的管道），它可以无限期地产生阶乘。然后我们用isolate组合它，它确保通过它传播的值不超过给定数量，然后我们用一个Consumer来组合它，它只对值求和并返回结果。在

Answer 3

基本上，是的：Haskell的lazy list很像Python的生成器，如果这些生成器可以轻松地进行克隆、缓存和组合。不是引发StopIteration，而是从递归函数返回{}，该函数可以将状态线程化到生成器中。在

由于自递归，它们会做一些更酷的事情。例如，您的阶乘生成器的生成方式更为习惯，如：

facts = 1 : zipWith (*) facts [1..]

或是腓骨肌：

^{pr2}$

一般来说，任何迭代循环都可以转换为递归算法，方法是将循环状态提升为函数的参数，然后递归地调用它以获得下一个循环循环。生成器就是这样的，但是我们在递归函数的每次迭代中都预先添加了一些元素，`go\\\uu=（stuff）：go\uuuu。在

因此，完美的等价物是：

ifact :: [Integer]
ifact = go 1 1
  where go f i = f : go (f * i) (i + 1)

sum_fact n = sum (take n ifact)

就什么是最快的，Haskell中绝对最快的可能是“for循环”：

sum_fact n = go 1 1 1
  where go acc fact i
          | i <= n = go (acc + fact) (fact * i) (i + 1)
          | otherwise = acc

事实上，这是“尾部递归”（调用go不会将对go的任何子调用传递给另一个函数，如(+)或{}），这意味着编译器可以将其打包到一个非常紧密的循环中，这就是为什么我将其与“for循环”进行比较，尽管这并不是Haskell的固有想法。在

上面的sum_fact n = sum (take n ifact)比这个稍慢，但比sum (take n facts)快，其中facts是用zipWith定义的。速度差异不是很大，我认为主要是因为内存分配不再被使用。在