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中是否有类似于这个生成器的行为,我认为懒惰会让所有员工都没有任何额外的概念.

例如,我们可以用我的Python ifact替换

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

实际上,懒惰列表可以这种方式使用.但是有一些微妙的差异:

• 列表是数据结构.所以你可以在评估它们之后保留它们,这可能是好的也可能是坏的(你可以避免重新计算值和@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

在这里,我们创建了一个Producer(无需输入的管道)无限期地产生阶乘.然后我们用isolate它组合,这确保通过它传播不超过给定数量的值,然后我们用一个Consumer只对值求和并返回结果的值组成它.

Answer 2

您的示例在内存使用方面不相同.很容易看出你是否*用a 替换+(这样数字不会太大),然后在n10 ^ 7这样的大例子上运行这两个例子.你的Haskell版本将占用大量内存,而python会保持较低的内存.

Python生成器不会生成值列表然后总结它.相反,该sum函数将从生成器逐个获取值并累积它们.因此,内存使用量将保持不变.

Haskell将懒惰地评估函数,但是为了计算,foldl1 (+) (take n fact)它必须评估完整的表达式.对于大型,n这将以同样的方式展开成一个巨大的表达(foldl (+) 0 [0..n]).有关评估和减少的更多详细信息,请访问:https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

您可以sum n使用foldl1'而不是foldl1上面的链接中所述来修复您的问题.正如@ user2407038在他的评论中解释的那样,你还需要保持fact本地化.以下在GHC中使用,具有恒定的内存使用:

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

请注意,在代替notfact内存的实际因子的情况下,考虑因素并不重要.数字将很快变大,任意精度算术会减慢速度,因此你无法获得较大的值n以便真正看到差异.

Answer 3

基本上,是的:Haskell的懒惰列表很像Python的生成器,如果这些生成器可以毫不费力地克隆,可缓存和可编译.而不是让StopIteration你[]从递归函数返回,这可以将状态线程转换为生成器.

由于自我递归,他们做了一些更酷的东西.例如,您的因子生成器更具惯用性生成,如:

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

或斐波那契:

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_fact n = sum (take n ifact)是比这个慢一点,但比快sum (take n facts),其中facts与定义zipWith.速度差异不是很大,我认为主要是归结为不再使用的内存分配.