非平凡的惰性求值

发布于 2024-12-11 06:01:27 字数 273 浏览 0 评论 0原文

我目前正在消化 Keegan McAllister 的精彩演讲为什么学习 Haskell？。在那里，他使用该代码片段

minimum = head . sort

来说明 Haskell 的惰性求值，指出 Haskell 中的minimum 的时间复杂度 O(n)。然而，我认为这个例子本质上是学术性的。因此，我要求提供一个更实际的示例，其中大部分中间计算都被丢弃，这一点并不是很明显。

原文

I'm currently digesting the nice presentation Why learn Haskell? by Keegan McAllister. There he uses the snippet

minimum = head . sort

as an illustration of Haskell's lazy evaluation by stating that minimum has time-complexity O(n) in Haskell. However, I think the example is kind of academic in nature. I'm therefore asking for a more practical example where it's not trivially apparent that most of the intermediate calculations are thrown away.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

娇女薄笑 2024-12-18 06:01:27

你写过人工智能吗？您必须通过树遍历函数线程化修剪信息（例如最大深度、相邻分支的最小成本或其他此类信息），这不是很烦人吗？这意味着每次你想要改进你的人工智能时，你都必须编写一个新的树遍历。那太愚蠢了。通过惰性求值，这不再是问题：编写一次树遍历函数，即可生成一个巨大的（甚至可能是无限的！）游戏树，并让您的消费者决定消耗多少树。
编写一个显示大量信息的 GUI？无论如何都想让它跑得快吗？在其他语言中，您可能必须编写仅渲染可见场景的代码。在 Haskell 中，您可以编写渲染整个场景的代码，然后选择要观察的像素。同样，渲染一个复杂的场景？为什么不计算各种细节级别的无限场景序列，并在程序运行时选择最合适的一个？
您编写了一个昂贵的函数，并决定记住它以提高速度。在其他语言中，这需要构建一个数据结构来跟踪您知道答案的函数的哪些输入，并在看到新输入时更新该结构。记住要使其线程安全——如果我们真的需要速度，我们也需要并行性！在 Haskell 中，您构建一个无限数据结构，其中每个可能的输入都有一个条目，并评估数据结构中与您关心的输入相对应的部分。线程安全随纯度而来。
这里的内容可能比之前的内容更加平淡。您是否曾经发现 && 和 || 并不是您唯一想要短路的东西？我当然有！例如，我喜欢使用 <|> 函数来组合 Maybe 值：它采用第一个实际具有值的参数。所以 只需 3 <|>什么都没有 = 只是 3; 什么都没有<|>刚好 7 = 刚好 7;和 什么都没有 <|>什么都没有=什么都没有。此外，它是短路的：如果结果证明它的第一个参数是 Just，它就不会费心进行计算来找出它的第二个参数是什么。
并且 <|> 不是内置于该语言中的；它是由图书馆附加的。也就是说：懒惰允许您编写全新的短路形式。（事实上，在 Haskell 中，甚至 (&&) 和 (||) 的短路行为也不是内置的编译器魔法：它们是自然产生的来自语言的语义及其在标准库中的定义。）

一般来说，这里的共同主题是您可以将值的生成与确定哪些值有趣分开。这使得事情变得更加可组合，因为制作者不需要知道有趣的内容的选择。

Have you ever written an AI? Isn't it annoying that you have to thread pruning information (e.g. maximum depth, the minimum cost of an adjacent branch, or other such information) through the tree traversal function? This means you have to write a new tree traversal every time you want to improve your AI. That's dumb. With lazy evaluation, this is no longer a problem: write your tree traversal function once, to produce a huge (maybe even infinite!) game tree, and let your consumer decide how much of it to consume.
Writing a GUI that shows lots of information? Want it to run fast anyway? In other languages, you might have to write code that renders only the visible scenes. In Haskell, you can write code that renders the whole scene, and then later choose which pixels to observe. Similarly, rendering a complicated scene? Why not compute an infinite sequence of scenes at various detail levels, and pick the most appropriate one as the program runs?
You write an expensive function, and decide to memoize it for speed. In other languages, this requires building a data structure that tracks which inputs for the function you know the answer to, and updating the structure as you see new inputs. Remember to make it thread safe -- if we really need speed, we need parallelism, too! In Haskell, you build an infinite data structure, with an entry for each possible input, and evaluate the parts of the data structure that correspond to the inputs you care about. Thread safety comes for free with purity.
Here's one that's perhaps a bit more prosaic than the previous ones. Have you ever found a time when && and || weren't the only things you wanted to be short-circuiting? I sure have! For example, I love the <|> function for combining Maybe values: it takes the first one of its arguments that actually has a value. So Just 3 <|> Nothing = Just 3; Nothing <|> Just 7 = Just 7; and Nothing <|> Nothing = Nothing. Moreover, it's short-circuiting: if it turns out that its first argument is a Just, it won't bother doing the computation required to figure out what its second argument is.
And <|> isn't built in to the language; it's tacked on by a library. That is: laziness allows you to write brand new short-circuiting forms. (Indeed, in Haskell, even the short-circuiting behavior of (&&) and (||) aren't built-in compiler magic: they arise naturally from the semantics of the language plus their definitions in the standard libraries.)

In general, the common theme here is that you can separate the production of values from the determination of which values are interesting to look at. This makes things more composable, because the choice of what is interesting to look at need not be known by the producer.

回复收藏 0 原文

哭了丶谁疼 2024-12-18 06:01:27

这是我昨天发布到另一个线程的一个著名示例。汉明数是没有任何大于 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)

用非惰性语言以合理的速度计算该数字需要更多的代码和头 -抓挠。这里有很多示例

Here's a well-known example I posted to another thread yesterday. Hamming numbers are numbers that don't have any prime factors larger than 5. I.e. they have the form 2^i*3^j*5^k. The first 20 of them are:

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

The 500000th one is:

1962938367679548095642112423564462631020433036610484123229980468750

The program that printed the 500000th one (after a brief moment of computation) is:

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)

Computing that number with reasonable speed in a non-lazy language takes quite a bit more code and head-scratching. There are a lot of examples here

回复收藏 0 原文