非平凡的懒惰评估

Question

我正在消化这个精彩的演示文稿为什么要学习Haskell？作者:Keegan McAllister.他在那里使用了片段

minimum = head . sort

作为Haskell懒惰评估的一个例子,说明在Haskell中minimum有时间复杂度 O(n).但是,我认为这个例子具有学术性质.因此,我要求一个更实际的例子,即大多数中间计算都被抛弃,这并不是显而易见的.

Answer 1

• 你有没有写过人工智能？通过树遍历函数来修剪修剪信息(例如最大深度,相邻分支的最小成本或其他此类信息)是不是很烦人？这意味着每次想要改进AI时都必须编写新的树遍历.那是愚蠢的.通过延迟评估,这不再是一个问题:编写一次树遍历函数,生成一个巨大的(甚至可能是无限的!)游戏树,让消费者决定消耗多少.

• 编写显示大量信息的GUI？希望它能够快速运行？在其他语言中,您可能必须编写仅呈现可见场景的代码.在Haskell中,您可以编写呈现整个场景的代码,然后选择要观察的像素.同样,渲染复杂的场景？为什么不在各种细节级别计算无限的场景序列,并在程序运行时选择最合适的场景？

• 你写了一个昂贵的功能,并决定记住它的速度.在其他语言中,这需要构建一个数据结构来跟踪您知道答案的函数的输入,并在看到新输入时更新结构.记得让线程安全 - 如果我们真的需要速度,我们也需要并行性!在Haskell中,您构建了一个无限的数据结构,每个可能的输入都有一个条目,并评估与您关注的输入相对应的数据结构部分.螺纹安全免费提供纯净.

• 这是一个可能比以前更平淡的一个.你有没有找到时间,&&而||不是你唯一想要短路的东西？我确定有!例如,我喜欢<|>组合Maybe值的函数:它接受其实际具有值的第一个参数.所以Just 3 <|> Nothing = Just 3; Nothing <|> Just 7 = Just 7; 和Nothing <|> Nothing = Nothing.而且,它是短路的:如果事实证明它的第一个参数是a Just,那么它就不会费心去做弄它第二个参数所需的计算.

  并<|>没有内置于语言中; 这是由图书馆强加的.那就是:懒惰让你可以写出全新的短路形式.(事实上,在Haskell,甚至短路行为(&&),并(||)没有内置的编译器魔术:他们从语言的标准库语义加上他们的定义中自然产生的)

一般来说,这里的共同主题是,您可以将值的生成与确定哪些值有趣的内容分开.这使得事物更容易组合,因为生产者不需要知道有趣的选择.

Answer 2

这是我昨天发布到另一个帖子的一个众所周知的例子.汉明数是没有任何素数因子大于5的数字.即它们具有2 ^ i*3 ^ j*5 ^ k的形式.前20个是:

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

第500000个是:

1962938367679548095642112423564462631020433036610484123229980468750

打印第500000个程序(经过短暂的计算后)的程序是:

merge xxs@(x:xs) yys@(y:ys) =
  case (x`compare`y) of
    LT -> x:merge xs yys
    EQ -> x:merge xs ys
    GT -> y:merge xxs ys

hamming = 1 : m 2 `merge` m 3 `merge` m 5
  where
    m k = map (k *) hamming

main = print (hamming !! 499999)

在非惰性语言中以合理的速度计算该数字需要相当多的代码和令人头疼的问题.这里有很多例子

Answer 3

考虑生成和消耗无限序列的第一个n元素。如果没有惰性求值，原始编码将在生成步骤中永远运行，并且永远不会消耗任何东西。使用惰性求值，只会生成与代码尝试使用的元素一样多的元素。