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

Question

在编程练习中，首先要求对阶乘函数进行编程，然后计算和：1! + 2! + 3! +... n!,O(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比该发生器类似的行为，我认为懒惰做所有的工作人员没有任何额外的概念。

例如，我们可以用

fact = scan1 (*) [1..] 

取代我的Python ifact进而解决行使如下：

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

我不知道如果这个解决方案是真正的“等效” Python的一个关于时间复杂度和内存使用。我会说Haskell的解决方案从不存储所有列表的事实，因为它们的元素只被使用一次。

我是对的还是完全错的？

---

编辑： 我应该检查更精确：

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

所以（我的执行）哈斯克尔存储结果，即使它不再使用。

Answer 1

您的示例是而不是等效于内存使用情况。很容易看出你是否用+替换*（以便数字不会太大），然后在诸如10^7的大n上运行这两个示例。你的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修复您的sum n，如上面链接中所述。正如@ user2407038在他的评论中解释的那样，你还需要在本地保留fact。在GHC下面的作品以恒定的内存使用：

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

注意的是，在地方notfact内存考虑实际的阶乘的情况下是不太关心的。数字会很快变大，任意精度算术会减慢速度，所以你将无法获得大数值n以便真正看到差异。

Answer 2

基本上，是的：如果这些生成器毫不费力地克隆，缓存和合成，Haskell的懒惰列表就像Python的生成器一样。您可以从递归函数返回[]来代替StopIteration，递归函数可以将状态线程化为生成器。

由于自递归，他们做了一些更酷的东西。

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

或Fibonaccis为：：例如，你的阶乘发生器更惯用等产生

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

一般而言任何迭代循环可以通过促进循环状态转换为递归算法函数的参数，然后递归地调用它来获得下一个循环。生成器就像那样，但是我们在递归函数的每次迭代前加上一些元素，'go ____ =（stuff）：go ____。因此

完美的等效是：

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定义的。速度差异不是很大，我认为大多数情况下只是归结为内存分配，不能再次使用。

Answer 3

事实上，懒惰列表可以这样使用。虽然有一些细微的差异：

• 列表是数据结构。所以你可以在对它们进行评估之后保留它们，这可以是好的也可以是不好的（你可以避免重新计算值和像@ChrisDrost描述的递归技巧，代价是保持内存不被释放）。
• 列表是纯的。在发电机中你可以计算副作用，你不能用列表来做这件事（这是经常需要的）。
• 由于Haskell是一种懒惰的语言，懒惰无处不在，如果您只是将一个程序从命令式语言转换为Haskell，内存需求可能会发生相当大的变化（如@RomanL在他的回答中所述）。

但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组合它，它只是求和值并返回结果。