懒惰评估为何有用？

我一直想知道懒惰评估为何有用.我还没有任何人以有道理的方式向我解释; 最重要的是它最终沸腾到"相信我".

注意:我不是指记忆.

1> mipadi..：

---

主要是因为它可以更有效 - 如果不打算使用值,则不需要计算值.例如,我可以将三个值传递给一个函数,但是根据条件表达式的顺序,实际上只能使用一个子集.在像C这样的语言中,无论如何都会计算所有三个值; 但在Haskell中,只计算必要的值.

它还允许像无限列表这样的酷东西.我不能在像C这样的语言中拥有无限列表,但在Haskell中,这没有问题.无限列表在数学的某些领域经常使用,因此有能力操作它们会很有用.

---

生成器使Python中的惰性列表变得容易,但其他惰性求值技术和数据结构明显不那么优雅.

---

Python通过迭代器对lazily评估了无限列表

---

实际上,你可以使用生成器和生成器表达式(它以与列表推导类似的方式工作)在Python中模拟无限列表:http://www.python.org/doc/2.5.2/ref/genexpr.html

---

我担心我不同意这个答案.我曾经认为懒惰是关于效率的,但是我已经大量使用Haskell,然后转换到Scala并比较经验,我不得不说懒惰很常见,但很少因为效率.我认为Edward Kmett对真正的原因有所了解.

---

我同样不同意,虽然由于严格的评估,在C中没有明确的无限列表概念,你可以通过使用thunks和传递函数轻松地在任何其他语言(实际上,在大多数每种懒惰语言的实际实现中)中播放相同的技巧.使用类似表达式生成的无限结构的有限前缀的指针.

2> Chris Eidhof..：

---

懒惰评估的一个有用示例是使用quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

如果我们现在想要找到列表的最小值,我们可以定义

minimum ls = head (quickSort ls)

首先对列表进行排序,然后获取列表的第一个元素.但是,由于懒惰的评估,只计算头部.例如,如果我们采用列表的最小值,则[2, 1, 3,]quickSort将首先过滤掉小于2的所有元素.然后它就做了quickSort(返回单例列表[1])已经足够了.由于懒惰的评估,其余的从未排序,节省了大量的计算时间.

这当然是一个非常简单的例子,但对于非常大的程序,懒惰对于同样的方式起作用.

但是,所有这些都有一个缺点:预测程序的运行时速度和内存使用量变得更加困难.这并不意味着懒惰的程序速度较慢或占用更多内存,但很高兴知道.

---

更一般地说,"take k $ quicksort list"只需要O(n + k log k)时间,其中`n = length list`.使用非惰性比较排序,这总是需要O(n log n)时间.

---

@Viclib用于查找n中的前k个元素的选择算法是O(n + k log k).当您使用惰性语言实现快速排序,并且只评估它足够远以确定前k个元素(停止评估之后)时,它会与非延迟选择算法进行完全相同的比较.

3> Edward KMETT..：

---

我发现懒惰的评估对很多事情很有用.

首先,所有现有的懒惰语言都是纯粹的,因为在懒惰的语言中很难推断副作用.

纯语言允许您使用等式推理来推理函数定义.

foo x = x + 3

不幸的是,在非延迟设置中,与懒惰设置相比,更多语句无法返回,因此在ML等语言中这样做不太有用.但是在一种懒惰的语言中,你可以安全地推理平等.

其次,像Haskell这样的惰性语言中不需要像ML中的"值限制"这样的东西.这导致语法的大量整理.ML喜欢的语言需要使用var或fun等关键字.在Haskell中,这些东西会崩溃为一个概念.

第三,懒惰让你编写非常实用的代码,可以分解.在Haskell中,编写一个函数体是很常见的:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

这可以让你通过理解函数体来"自上而下"工作.ML类语言强制您使用严格评估的let.因此,你不敢把let子句"提升"到函数的主体,因为如果它昂贵(或有副作用),你不希望它总是被评估.Haskell可以明确地将细节"推送"到where子句,因为它知道该子句的内容只会根据需要进行评估.

在实践中,我们倾向于使用警卫并进一步崩溃:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

第四,懒惰有时会提供更优雅的某些算法表达.Haskell中的一个懒惰的"快速排序"是一个单行,并且有一个好处,如果你只看前几个项目,你只需支付与选择那些项目的成本成比例的成本.没有什么可以阻止您严格执行此操作,但您可能不得不每次重新编码算法以实现相同的渐近性能.

第五,懒惰允许您在语言中定义新的控制结构.你不能写一个新的'if .. then .. else ..'就像用严格的语言构造一样.如果您尝试定义如下函数:

if' True x y = x
if' False x y = y

在严格的语言中,无论条件值如何,都将评估两个分支.考虑循环时会变得更糟.所有严格的解决方案都要求语言为您提供某种引用或显式lambda构造.

最后,同样地,在类型系统中处理副作用的一些最佳机制,例如monad,实际上只能在惰性环境中有效表达.这可以通过比较F#的工作流程与Haskell Monads的复杂性来见证.(你可以用一种严格的语言定义一个单子,但不幸的是,由于缺乏懒惰,你经常会失败一两个单一的法律,而工作流程通过比较来获取大量严格的行李.)

---

此外,虽然懒惰的语言必须纯粹在技术上是正确的(R作为一个例子),但是不纯的懒惰语言确实可以做很奇怪的事情(R作为例子).

---

非常好; 这些都是真正的答案.我曾经认为这是关于效率(延迟计算以后),直到我使用Haskell一大笔钱,并且发现这根本不是原因.

---

当然有.在一个严格的语言递归`let`是一个危险的野兽,在R6RS计划中,它允许随机的`#f`出现在你的术语中,无论在哪里打结,严格导致一个循环!没有双关语意图,但严格来说,更加递归的"let"绑定在懒惰的语言中是明智的.严格也加剧了"where"根本没有办法排序相对效果的事实,除了SCC,它是一个声明级别的结构,它的效果可以严格地按任何顺序发生,即使你有一个纯粹的语言你风与#f`问题一起.严格的"where"使您的代码充满了非本地关注点.

---

@PaulBone你在说什么？懒惰对控制结构有很大帮助.如果你用严格的语言定义自己的控制结构,它将要么必须使用一堆lambda或类似的,否则它会很糟糕.因为`ifFunc(True,x,y)`将同时评估'x`和`y`而不仅仅是'x`.

---

你能解释一下懒惰有助于避免价值限制吗？我无法理解这一点.

4> Thomas Danec..：

---

普通订单评估与惰性评估之间存在差异(如Haskell中所示).

square x = x * x

评估以下表达式......

square (square (square 2))

......热切评价:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

...正常的订单评估:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

...懒惰的评价:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

那是因为懒惰的评估会查看语法树并进行树转换......

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

...而正常的订单评估只进行文本扩展.

这就是为什么我们在使用延迟评估时会变得更强大(评估比其他策略更频繁地终止),而性能等同于急切评估(至少在O表示法中).

5> Norman Ramse..：

---

如果你相信西蒙佩顿琼斯,懒惰的评价本身并不重要,只是作为一个"头发衬衫",迫使设计师保持语言纯洁.我发现自己同情这种观点.

理查德伯德,约翰休斯以及较小范围的拉尔夫欣泽能够通过懒惰的评价做出惊人的事情.阅读他们的作品将有助于你欣赏它.好的起点是Bird的华丽数独求解器和Hughes关于为什么功能编程很重要的论文.

6> Alexey..：

---

与CPU相关的惰性评估与与RAM相关的垃圾收集相同.GC允许您假装您拥有无限量的内存,因此可以根据需要在内存中请求尽可能多的对象.运行时将自动回收不可用的对象.LE允许您假装您拥有无限的计算资源 - 您可以根据需要进行尽可能多的计算.运行时不会执行不必​​要的(对于给定的情况)计算.

这些"假装"模型的实际优势是什么？它会从管理资源中释放开发人员(在某种程度上),并从您的源中删除一些样板代码.但更重要的是,您可以在更广泛的上下文中有效地重用您的解决方案.

想象一下,你有一个数字S列表和一个数字N.你需要找到最接近列表S的数字N数字M.你可以有两个上下文:单个N和一些N的列表L(对于每个N在L中的ei)你在S中查找最近的M).如果你使用懒惰的评价,您可以排序S和应用二进制搜索找到最接近M至N.为了获得良好的懒惰排序将需要O(大小(S))的单N和O(LN步骤(大小(S))*(大小(S)+大小(L)))均匀分布的L的步骤.如果您没有延迟评估来实现最佳效率,则必须为每个上下文实现算法.

7> Paul Johnson..：

---

考虑一个tic-tac-toe计划.这有四个功能:

移动生成功能,它采用当前板并生成一个新板的列表,每个板都应用一个移动.

然后有一个"移动树"功能,它应用移动生成功能来导出可能跟随此移动的所有可能的板位置.

有一个minimax函数可以遍历树(或者可能只是它的一部分)以找到最佳的下一步.

有一个棋盘评估功能,可以确定其中一个球员是否赢了.

这创造了一个明确的关注点分离.特别是移动生成函数和板评估函数是唯一需要理解游戏规则的函数:移动树和极小极大函数是完全可重用的.

现在让我们尝试实现国际象棋而不是井字游戏.在"渴望"(即常规)语言中,这将不起作用,因为移动树将不适合存储器.因此,现在需要将板评估和移动生成函数与移动树和极小极大逻辑混合在一起,因为必须使用极小极大逻辑来决定生成哪些移动.我们漂亮干净的模块化结构消失了.

然而,在惰性语言中,移动树的元素仅响应于来自minimax函数的要求而生成:在我们让minimax在顶部元素上松散之前,不需要生成整个移动树.所以我们干净的模块化结构仍然适用于真实游戏.

---

是的,这就是我的观点.渴望的语言可以为琐碎的游戏提供一个干净的结构,但必须妥协任何真实的结构.懒惰语言没有这个问题.

---

但公平地说,懒惰的评估会导致它自己的记忆问题.对于人们来说,为什么haskell正在为某些内容消耗内存并不常见,因为在一次急切的评估中,它会有内存消耗O(1)

8> Edward Z. Ya..：

---

还有两点我不相信已在讨论中提出过.

懒惰是并发环境中的同步机制.它是一种轻量级且简单的方法,可以创建对某些计算的引用,并在许多线程中共享其结果.如果多个线程尝试访问未评估的值,则只有其中一个执行它,而其他线程将相应地阻塞,一旦它变为可用就接收该值.

懒惰是在纯粹环境中分摊数据结构的基础.这是Okasaki在Purely Functional Data Structures中详细描述的,但基本思想是懒惰评估是一种受控形式的变异,对于允许我们有效地实现某些类型的数据结构至关重要.虽然我们经常谈到懒惰迫使我们穿纯洁的运动衫,但另一种方式也适用:它们是一对协同语言特征.

9> yfeldblum..：

---

当您打开计算机并且Windows禁止在Windows资源管理器中打开硬盘驱动器上的每个目录并且不启动计算机上安装的每个程序时,直到您指示需要某个目录或需要某个程序,是"懒惰"的评价.

"懒惰"评估是在需要时执行操作.当它是编程语言或库的一个特性时很有用,因为通常更难以自己实现惰性求值而不是简单地预先计算所有内容.

10> Romain Linso..：

---

考虑一下:

if (conditionOne && conditionTwo) {
  doSomething();
}

仅当conditionOne为true 且 conditionTwo为true时,才会执行doSomething()方法.在conditionOne为false的情况下,为什么需要计算conditionTwo的结果？在这种情况下,条件2的评估将浪费时间,特别是如果您的条件是某些方法过程的结果.

这是懒惰评价兴趣的一个例子......

---

事实上,短路是懒惰评估的一个特例.懒惰的评估显然不仅包括短路.或者,短路有什么超过懒惰评估？

---

我认为短路是一种慵懒评估的退化情况,但绝对不是一种常见的思考方式.

---

这是懒惰的评估,因为conditionTwo仅在真正需要时计算(即如果conditionOne为真).

---

@Juliet:你对'懒惰'有一个强烈的定义.使用两个参数的函数示例与if语句短路不同.if语句的短路避免了不必要的计算.我认为与您的示例更好的比较是Visual Basic的运算符"andalso",它强制要求评估两个条件

11> Mathematical..：

---

它可以提高效率.这是一个看起来很明显的,但实际上并不是最重要的.(另请注意,懒惰可以杀死效率太-这个事实是不会立即明显然而,通过存储了大量的临时结果,而不是立即计算它们,就可以使用了一个巨大的RAM量.)

它允许您在普通用户级代码中定义流控制结构,而不是将其硬编码到语言中.(例如,Java有for循环; Haskell有一个for函数.Java有异常处理; Haskell有各种类型的异常monad.C#有goto; Haskell有continuation monad ...)

它允许您从算法中分离算法以生成数据,以决定生成多少数据.您可以编写一个函数来生成一个名义上无限的结果列表,另一个函数可以根据需要处理该列表中的大部分内容.更重要的是,您可以拥有五个生成器功能和五个消费者功能,并且您可以有效地生成任何组合 - 而不是手动编码5 x 5 = 25个同时组合两个动作的功能.(!)我们都知道脱钩是件好事.

它或多或少地迫使你设计一种纯粹的功能语言.采取捷径总是诱人的,但是用懒惰的语言,最轻微的杂质会使你的代码变得非常难以预测,这极大地阻碍了快捷方式的发展.

12> Juliet..：

---

懒惰的一个巨大好处是能够使用合理的摊销边界编写不可变数据结构.一个简单的例子是不可变堆栈(使用F#):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

代码是合理的,但是在最佳,最差和平均情况下,附加两个堆栈x和y需要O(x长度)时间.附加两个堆栈是单片操作,它接触堆栈x中的所有节点.

我们可以将数据结构重写为惰性堆栈:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazy通过暂停其构造函数中的代码评估来工作.使用后评估.Force(),返回值将被缓存并在每个后续时间重用.Force().

对于惰性版本,追加是一个O(1)操作:它返回1个节点并暂停列表的实际重建.当您获得此列表的头部时,它将评估节点的内容,强制它返回头部并使用其余元素创建一个暂停,因此取列表的头部是O(1)操作.

因此,我们的惰性列表处于不断重建的状态,在遍历其所有元素之前,您不需要为重建此列表付出代价.使用懒惰,此列表支持O(1)consing和append.有趣的是,由于我们不会在访问节点之前对其进行评估,因此完全有可能构建一个具有潜在无限元素的列表.

上面的数据结构不需要在每次遍历时重新计算节点,因此它们与.NET中的vanilla IEnumerables明显不同.

13> Vinko Vrsalo..：

---

此摘要显示了惰性评估和非惰性评估之间的区别。当然，这个斐波那契函数本身可以被优化并使用惰性求值而不是递归，但这会破坏示例。

假设我们可能必须对某些东西使用前20个数字，而不必进行惰性评估，所有这20个数字都必须预先生成，但是对于惰性评估，它们只会根据需要生成。因此，您仅在需要时支付计算价格。

样品输出

不偷懒一代：0.023373
惰性代：0.000009
非延迟输出：0.000921
延迟输出：0.024205

import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)

14> 小智..：

---

延迟评估对数据结构最有用.您可以定义一个数组或向量,以归纳方式仅指定结构中的某些点,并根据整个数组表示所有其他点.这使您可以非常简洁地生成数据结构并具有高运行时性能.

要了解这一点,您可以查看我的神经网络库,名为instinct.它大量使用懒惰评估优雅和高性能.例如,我完全摆脱了传统的命令式激活计算.一个简单的懒惰表达式为我做了一切.

这用于激活函数和反向传播学习算法(我只能发布两个链接,因此您需要自己查找模块中的learnPat函数AI.Instinct.Train.Delta).传统上都需要更复杂的迭代算法.