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..]

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

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

基本上，是的：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 loops”进行比较，尽管这并不是Haskell的原生想法。

上面的sum_factn=sum（接受n个事实）比这个慢一点，但比sum（接受n个事实）快一点，其中事实是用zipAnd定义的。速度差异不是很大，我认为主要是由于不再使用的内存分配。

Answer 2

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

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

Haskell将懒散地计算函数，但为了计算sayfoldl1（）（以事实为例）它必须计算完整的表达式。对于大型表达式，这将以与大型表达式相同的方式展开（foldl（）0[0..n]）。有关评估和减少的更多详细信息，请参见：https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl'.

您可以使用foldl1'而不是上面链接中描述的foldl1来修复您的sum n。正如@user2407038在他的评论中解释的那样，您还需要将事实保持在本地。以下操作在GHC中使用恒定内存：

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

请注意，如果用实际阶乘代替Not事实，内存考虑就不那么重要了。数字会很快变大，任意精度的算术会减慢速度，所以你无法得到n的大值来实际看到差异。

Answer 3

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

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

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

它们有几个优点，特别是您可以创建复杂的管道，并且可以将它们基于选定的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

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