为什么懒惰评估有用?

我一直在想,为什么懒惰的评估是有用的。 我还没有任何人以一种合理的方式向我解释; 大多数情况下,它最终会熬到“相信我”。

注意:我不是指记忆。

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

它也允许像无限列表这样的酷东西。 我不能在像C这样的语言中使用无限的列表,但是在Haskell中,这没有问题。 无限列表经常用在某些math领域,所以有能力操纵它们是有用的。

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

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

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

 minimum ls = head (quickSort ls) 

首先对列表进行sorting,然后获取列表的第一个元素。 但是,由于懒惰的评价,只有头部被计算。 例如,如果我们取最小值[2, 1, 3,] 2,1,3 [2, 1, 3,] quickSort将首先过滤出所有小于2的元素。 然后它快速sorting(返回单例列表[1])已经足够了。 由于懒惰的评估,其余从不sorting,节省了大量的计算时间。

这当然是一个非常简单的例子,但懒惰对于非常大的程序也是一样的。

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

我发现懒惰的评估有用的一些事情。

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

纯语言让你使用等式推理来推理函数定义。

 foo x = x + 3 

不幸的是,在一个非懒惰的设置,更多的语句不能返回比在懒惰的设置,所以这对ML等语言不太有用。 但是用一种懒惰的语言,你可以安全地推理平等。

其次,像Haskell这样的懒惰语言中不需要像ML中的“价值限制”那样的许多东西。 这导致了句法的极度混乱。 ML喜欢的语言需要使用像var或fun这样的关键字。 在Haskell中,这些东西倒塌成一个概念。

第三,懒惰可以让你写出非常实用的代码,可以被理解成碎片。 在Haskell中,编写一个函数体是很常见的:

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

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

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

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

第四,懒惰有时会提供某些algorithm更优雅的expression。 在Haskell中,一个懒惰的“快速sorting”是一个单线程,并且有一个好处,如果你只看前面几个项目,你只需支付与select这些项目成本成正比的成本。 没有什么能够阻止你严格执行这个操作,但是你可能不得不每次重新编码这个algorithm来达到同样的渐进性能。

第五,懒惰可以让你用语言来定义新的控制结构。 你不能用严格的语言编写一个新的“if .. then .. else”。 如果您尝试定义一个函数,如:

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

以严格的语言,那么无论条件值如何,都将评估两个分支。 当你考虑循环时,情况会变得更糟。 所有严格的解决scheme都要求语言为您提供某种引用或明确的lambda结构。

最后,同样地,处理types体系副作用的一些最好的机制,例如monad,实际上只能在懒惰的环境中有效地expression。 这可以通过比较F#的工作stream程和Haskell Monads的复杂性来见证。 (你可以用一种严格的语言来定义一个monad,但是不幸的是,由于缺乏懒惰和工作stream程,通常会比较挑剔一堆严格的行李。

正常顺序评估和懒惰评估(就像在Haskell中)是有区别的。

 square x = x * x 

评估以下expression式…

 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 

…而正常的顺序评估只能做文本扩展。

这就是为什么我们在使用懒惰评估时变得更加强大(评估终止更多的时候,然后是其他策略),而性能等同于急切的评估(至less在O-notation中)。

如果你相信西蒙·佩顿·琼斯(Simon Peyton Jones),懒惰的评价本身并不重要只是作为一件“发衬衫”,迫使devise师保持纯正的语言。 我发现自己同情这个观点。

理查德·伯德(Richard Bird),约翰·休斯(John Hughes),以及拉尔夫·欣泽(Ralf Hinze)都可以用懒惰的评价来做出惊人的事情。 阅读他们的工作将有助于你欣赏它。 为了给出好的起点, Bird的macros伟的Sudoku求解器和Hughes关于Why Functional Programming Matters的论文。

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

这些“假装”模型的实际优势是什么? 它释放开发者(在某种程度上)pipe理资源,并从源代码中删除一些样板代码。 但更重要的是,您可以在更广泛的环境中有效地重用您的解决scheme。

假设您有一个数字S和一个数字N的列表。您需要从列表S中find最接近数字N的数字M.您可以有两个上下文:单个N和一些N的列表L(对于L中的每个N你在S中查找最接近的M)。 如果使用惰性评估,则可以对S进行sorting并应用二进制search以find最接近的M到N.对于良好的惰性sorting,对于单个N和O(ln(size(S))*,将需要O(size(S) (大小(S)+大小(L)))步骤为平等分布L.如果你没有懒惰的评估来达到最佳的效率,你必须为每个上下文实现algorithm。

考虑一个tic-tac-toe程序。 这有四个function:

  • 移动生成function,使用当前板,并生成每个应用了一次移动的新板的列表。
  • 然后有一个“移动树”function,应用移动生成function来导出所有可能的棋盘位置。
  • 有一个minimax函数可以走树(或可能只是其中的一部分)来find最好的下一步。
  • 有一个董事会评估function,确定是否有一名球员获胜。

这创造了一个很好的清晰的关注点分离。 特别是移动生成函数和棋盘评价函数是唯一需要了解游戏规则的函数:移动树和极小极大函数是完全可重用的。

现在让我们尝试实现国际象棋,而不是井字棋。 在“渴望”(即常规)语言中,这将不起作用,因为移动树不适合内存。 所以现在的棋盘评估和移动生成function需要与移动树和极小极大逻辑混合在一起,因为极小极大逻辑必须被用来决定哪些棋步要生成。 我们干净的模块化结构消失了。

然而,在一个懒惰的语言中,移动树的元素只是响应来自极小极大函数的需求而生成的:在让极大极小元素放在顶层元素之前,不需要生成整个移动树。 所以我们干净的模块化结构仍然在真实的游戏中运作。

这里还有两点我不相信已经在讨论中提出来了。

  1. 懒惰是并发环境中的同步机制。 这是一个轻量级和简单的方法来创build一个计算的参考,并分享其结果之间的许multithreading。 如果多个线程尝试访问一个未评估的值,则只有其中一个线程会执行它,其他线程将相应地进行阻塞,一旦该线程可用,就会收到该值。

  2. 懒惰是在纯粹的环境中分摊数据结构的基础。 这在Okasaki的Purely Functional Data Structures中有详细描述,但基本思想是懒惰评估是一种控制forms的突变,对于允许我们有效地实现某些types的数据结构至关重要。 虽然我们经常说懒惰迫使我们穿纯色的毛衫,但另一方面也适用:它们是一对协同的语言特征。

当您打开计算机和Windows时,不会打开Windows资源pipe理器中硬盘驱动器上的每个目录,也不会启动安装在计算机上的每个程序,除非您指出需要某个目录或需要某个程序,是“懒惰”的评价。

“懒惰”评估是在需要时执行操作。 当它是编程语言或库的一个特性时,它是有用的,因为通常难以自己实现惰性评估,而不是简单地预先计算所有的事情。

  1. 它可以提高效率。 这看起来很明显,但实际上并不是最重要的。 (还要注意,懒惰也会使效率下降 – 这个事实并不是很明显,但是通过暂时存储大量的临时结果,而不是立即计算,就可以占用大量的RAM)。

  2. 它允许您在普通用户级代码中定义stream控制结构,而不是将其硬编码到语言中。 (例如,Java有for循环; Haskell有for函数,Java有exception处理; Haskell有各种types的exceptionmonad,C#有goto ; Haskell有继续monad …)

  3. 它可以让您从algorithm中分离出用于生成数据的algorithm,以决定生成多less数据。 您可以编写一个函数来生成一个概念无限的结果列表,另一个函数可以根据需要处理这个列表。 更重要的是,你可以有五个发电机function和五个消费者function,你可以有效地产生任何组合 – 而不是手动编码5×5 = 25个function,一次结合两个行动。 (!)我们都知道去耦是一件好事。

  4. 它或多或less地迫使你devise一个纯粹的function语言。 采取快捷方式总是很有诱惑力,但是用一种懒惰的语言,最细微的杂质使得你的代码难以预测,这极大地阻碍了快捷方式的实施。

考虑一下:

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

只有当conditionOne为true conditionTwo为true时,方法doSomething()才会被执行。 在conditionOne为false的情况下,为什么需要计算conditionTwo的结果? conditionTwo的评估在这种情况下是浪费时间,特别是如果您的情况是某些方法过程的结果。

这是懒惰的评估兴趣的一个例子…

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

 type 'a stack = | EmptyStack | StackNode of 'a * 'a stack let rec append xy = 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 xy = match x with | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y)) | Empty -> y 

lazy作品通过暂停在其构造函数中的代码评估。 一旦使用.Force()进行评估,返回值就被caching,并在每个后续的.Force()重用。

使用懒惰版本,附加操作是O(1)操作:返回1个节点并挂起列表的实际重build。 当你得到这个列表的头部时,它将评估节点的内容,迫使它返回头部,并与剩余的元素一起创build一个悬挂,所以取出列表的头部是O(1)操作。

所以,我们的懒惰列表处于持续重build的状态,在遍历所有元素之前,您不需要花费重build这个列表的代价。 使用懒惰,这个列表支持O(1)的select和追加。 有趣的是,由于我们不评估节点,直到它们被访问,它完全可能构build一个有可能无限元素的列表。

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

懒惰评估对于数据结构是最有用的。 您可以定义一个数组或vector,以感应方式指定结构中的某些点,并根据整个数组表示所有其他点。 这使您可以非常简洁地生成数据结构,并具有较高的运行时性能。

要看到这个在行动,你可以看看我的neural network库称为本能 。 它优雅,高效地大量使用懒惰的评价。 例如,我完全摆脱了传统上强制性的激活计算。 一个简单的懒惰expression为我做了一切。

这个例子在激活函数和后向传播学习algorithm(我只能发布两个链接,所以你需要在AI.Instinct.Train.Delta模块中查找learnPat函数)。 传统上都需要更复杂的迭代algorithm。

这段代码显示了懒惰和不懒惰评估之间的区别。 当然这个fibonacci函数本身可以被优化,并且使用懒惰评估而不是recursion,但是这会破坏这个例子。

假设我们可能必须使用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) 

其他人已经给出了所有的大理由,但我认为有用的练习来帮助理解为什么懒惰是一个严格的语言尝试和写一个定点function。

在Haskell中,一个定点函数是非常容易的:

 fix f = f (fix f) 

这扩大到

 f (f (f .... 

但是因为Haskell是懒惰的,那无限的计算链是没有问题的; 评价是“从内到外”完成的,一切都很好:

 fact = fix $ \fn -> if n == 0 then 1 else n * f (n-1) 

重要的是,重要的是不要fix懒惰,但这是懒惰的。 一旦你获得了一个严格的f ,你可以把你的手放在空中放弃,或者eta扩展它,把杂乱的东西填满。 (这很像诺亚所说的那种严格/懒惰的图书馆 ,而不是语言)。

现在设想在严格的Scala中编写相同的函数:

 def fix[A](f: A => A): A = f(fix(f)) val fact = fix[Int=>Int] { f => n => if (n == 0) 1 else n*f(n-1) } 

你当然会得到一个堆栈溢出。 如果你想让它工作,你需要按需要调用f参数:

 def fix[A](f: (=>A) => A): A = f(fix(f)) def fact1(f: =>Int=>Int) = (n: Int) => if (n == 0) 1 else n*f(n-1) val fact = fix(fact1) 

我不知道你现在怎么看待事情,但是我认为将懒惰评价看作是一个图书馆问题而不是语言特征是有用的。

我的意思是,在严格的语言中,我可以通过构build一些数据结构来实现懒惰的评估,而在懒惰的语言(至lessHaskell)中,我可以在需要的时候要求严格。 因此,语言的select并不能真正使你的程序变得懒惰或不懒惰,而只是简单的影响你默认得到的。

一旦你这样想,那么想想你写的一个数据结构的所有地方,你以后可以使用它来生成数据(在此之前不要过多地看),你会看到很多用于懒惰评价。

我使用的懒惰评估最有用的方法是以特定顺序调用一系列子函数。 如果这些子函数中的任何一个失败(返回false),调用函数需要立即返回。 所以我可以这样做:

 bool Function(void) { if (!SubFunction1()) return false; if (!SubFunction2()) return false; if (!SubFunction3()) return false; (etc) return true; } 

或者,更优雅的解决scheme:

 bool Function(void) { if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) ) return false; return true; } 

一旦你开始使用它,你会看到越来越多的机会使用它。

没有懒惰的评估,你将不被允许写这样的东西:

  if( obj != null && obj.Value == correctValue ) { // do smth } 

其中,懒惰的语言允许多维无限的数据结构。

虽然scheme,python等允许一维无限的数据结构与stream,你只能沿着一个维度。

懒惰对于相同的边缘问题是有用的,但是值得注意的是这个链接中提到的协程连接。

懒惰评估是穷人的等式推理(可以预期,理想情况下,可以从涉及的types和操作属性中推导出代码的属性)。

例子,它工作得很好: sum . take 10 $ [1..10000000000] sum . take 10 $ [1..10000000000] 。 我们不介意将其减less到10个数字的总和,而不是仅仅一个直接和简单的数字计算。 没有懒惰的评估当然这将创造一个巨大的内存列表只是使用其前10个元素。 这肯定会很慢,并且可能会导致内存不足的错误。

例如,它不如我们想要的那么好: sum . take 1000000 . drop 500 $ cycle [1..20] sum . take 1000000 . drop 500 $ cycle [1..20] sum . take 1000000 . drop 500 $ cycle [1..20] 。 即使在一个循环中,而不是在一个列表中,实际上会将这100 000个数字相加, 仍然应该减less到只有一个直接的数值计算,几乎没有条件和公式。 总结一百万个数字好很多。 即使在一个循环中,而不是在一个列表(即在森林砍伐优化之后)。


另一件事是,它可以在尾部recursionmodulo风格编码,它只是工作

比照 相关的答案 。

如果通过“懒惰评价”你的意思就像在布尔组合,就像在

  if (ConditionA && ConditionB) ... 

那么答案就是程序消耗的CPU周期越less,运行的速度就越快…如果一大块处理指令对程序的结果没有影响,那么这是不必要的(因此浪费的时间)无论如何执行它们…

如果otoh,你的意思是我所知道的“懒惰初始化”,如:

 class Employee { private int supervisorId; private Employee supervisor; public Employee(int employeeId) { // code to call database and fetch employee record, and // populate all private data fields, EXCEPT supervisor } public Employee Supervisor { get { return supervisor?? (supervisor = new Employee(supervisorId)); } } } 

那么,这种技术允许使用类的客户端代码避免需要为Supervisor数据logging调用数据库,除非使用Employee对象的客户端需要访问主pipe的数据…这使得更快地实例化Employee的过程,但是当你需要主pipe,第一次调用主pipe属性将触发数据库调用,数据将被提取并可用…

摘录自高阶函数

让我们find可以被3829整除的100,000以下的最大数字。为了做到这一点,我们将过滤一系列我们知道解决scheme的可能性。

 largestDivisible :: (Integral a) => a largestDivisible = head (filter p [100000,99999..]) where px = x `mod` 3829 == 0 

我们首先列出所有低于10万的数字,下降。 然后我们用谓词过滤它,因为数字是按降序排列的,满足我们谓词的最大数是过滤列表的第一个元素。 我们甚至不需要为我们的起始组使用有限的列表。 这又是懒惰的行动。 因为我们只使用过滤列表的头部,所以过滤的列表是有限还是无限无关紧要。 当find第一个适当的解决scheme时,评估停止。