非平凡的惰性求值

Question

我目前正在消化Keegan McAllister的演讲 Why learn Haskell?，他在那里使用了这个片段

minimum = head . sort

举例说明Haskell的惰性求值，指出在Haskell中minimum函数的时间复杂度为O(n)。然而，我认为这个例子有点学术化。因此，我要求一个更实际的例子，在这个例子中，大部分中间计算不能被轻易地抛弃。

- Nordlöw

---

例子是学术性的，但惰性求值的好处并不明显，这两者之间有所区别。你为什么需要后者？看到现实世界的代码可以受益于惰性求值难道不足够了吗？ - user395760

“计算机科学中的所有问题都可以通过另一层间接性来解决。” 懒惰也是一种间接性。 - Will Ness

https://www.reddit.com/r/haskell/comments/5xge0v/today_i_used_laziness_for/?limit=500 有许多不错的例子。 - unhammer

Answer 1

• 你是否曾经编写过人工智能程序？那么你一定深有体会，在树遍历函数中传递剪枝信息（例如最大深度，相邻分支的最小成本或其他类似信息）是多么令人烦恼。这意味着每次想要改进AI时，都必须重新编写树遍历函数。但有了惰性评估，这就不再是问题了：只需编写一次树遍历函数即可生成一个巨大的（甚至可能是无限的！）游戏树，让使用者决定需要消耗的部分。

• 想要编写一个显示大量信息的GUI吗？希望程序在运行时仍然快速吗？在其他语言中，您可能需要编写仅渲染可见场景的代码。但在Haskell中，您可以编写代码以渲染整个场景，然后稍后选择要观察的像素。同样地，要渲染复杂的场景吗？何不计算各种精细级别的无限场景序列，并在程序运行时选择最合适的场景？

• 你编写了一个代价高昂的函数，并决定为了加速它而进行备忘录化处理。在其他语言中，这需要构建一个数据结构，跟踪您已知函数输入的答案，并在看到新的输入时更新该结构。别忘了使其线程安全--如果我们真的需要速度，我们还需要并行性！但在Haskell中，你可以构建一个无限的数据结构，为每个可能的输入都创建一个条目，并评估与您关心的输入相对应的数据结构部分。纯洁性带来的不可变性自然保证了线程安全。

这里讲述的内容可能比之前的那些内容朴素一些。你是否曾经遇到过想要短路的东西不仅仅是&&和||？我肯定有！例如，我喜欢使用<|>函数来组合Maybe值：它获取其参数中实际具有值的第一个值。因此，Just 3 <|> Nothing = Just 3；Nothing <|> Just 7 = Just 7；Nothing <|> Nothing = Nothing。此外，它还具有短路效应：如果发现第一个参数是Just，则不会进行计算以确定第二个参数。

而且，<|>不是内置在语言中的；它是由库添加的。也就是说：惰性允许您编写全新的短路形式。（实际上，在Haskell中，(&&)和(||)的短路行为甚至不是内置的编译器魔法：它们自然地从语言的语义加上标准库中它们的定义中产生。）

总的来说，这里的共同主题是您可以将值的生成与决定哪些值有趣分开。这使得事物更具可组合性，因为生产者不需要知道有趣的内容选择。

- Daniel Wagner

---

哇，令人信服的论点——在我看来，Haskell 的未来前景很有希望。所以 <|> 运算符相当于（Emacs-）Lisp 中对可能始终为 nil 的对象的 or 行为，对吧？无论如何，我真的很想在其他语言中使用这种行为。 - Nordlöw

“线程修剪信息”是什么意思？它是特定树枝性能统计的某种簿记吗？ - Nordlöw

@Nordlöw 是的，完全正确。比如说，当你第一次实现一个 AI 并且只是想快速实现时，你可能会决定使用暴力搜索法进行 n 层深度的搜索。但是，你写的用于 n 层深度搜索的函数必须要做两个任务：一个是搜索游戏树，另一个是跟踪你已经搜索了多少层。后来，当你决定使用 alpha-beta 剪枝而不是暴力搜索时，由于这两个任务在一个函数中交织在一起，你就有些束手无策了。懒惰允许你分离搜索游戏树和剪枝搜索树的任务。 - Daniel Wagner

当然，如果可以存储所有可能的结果，记忆化只会变得更简单。如果你只能够记忆化最常被评估的_n_个结果（但在编译时不知道这些结果是哪些），Haskell的纯度实际上会使它更难实现。 - leftaroundabout

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)

在非惰性语言中以合理的速度计算该数字需要编写更多代码并进行深思熟虑。这里有很多示例。

- solrize

Answer 3

考虑生成和使用无限序列的前 n 个元素。如果没有惰性计算，那么生成步骤将永远运行下去，而不会消耗任何东西。有了惰性计算，只要代码尝试消耗多少元素，就会生成多少元素。

- Phil Miller