懒惰与函数组合（Haskell，Erlang）

Question

有人能否解释或提供一些关于在惰性计算中如何进行函数组合的资源？

例如，filter (/='W') . map toUpper $ "justaword" 在 Haskell 中与其非惰性计算的 Erlang 版本相比是如何工作的？

- Adi

Answer 1

每次需要另一个字符（或结束通知）时，下一个字符（如果有）将映射为大写字母，并与“W”进行比较，如果不相等，则传递。

filter (/= 'W') . map toUpper $ "justaword"
~> filter (/= 'W') (toUpper 'j' : map toUpper "ustaword")
~> filter (/= 'W') ('J' : map toUpper "ustaword")
~> 'J' : filter (/= 'W') (map toUpper "ustaword")

现在第一个字符已经可以使用了，因此对于像null这样的查询或take 1这样的函数，不需要进行更多的工作。如果消费者需要更多的字符，则会逐个生成字符，直到达到字符串的末尾。

例如：

Prelude Data.Char> take 10 . filter (/= 'W') . map toUpper $ repeat 't'
"TTTTTTTTTT"

repeat 产生无限列表，但只要消耗有限部分，计算就会在有限时间内完成。然而，take 10 . filter (/= 'W') . map toUpper $ repeat 'w' 将不会终止，因为没有任何生成的字符通过 filter 到达 take 10。

- Daniel Fischer

---

非常感谢您的积极回应 :) 是否有可能用严格语言编写此代码（而不是模拟懒惰）？或者在严格语言中，列表将被遍历两次，一次用于映射，一次用于过滤，从开头开始？ - Adi

@Adi：是的，将会有两次列表遍历。map 将返回一个新的中间列表，该列表将传递给 filter，filter 将对其进行遍历并返回另一个列表。 - newacct

在一个严格（渴望的）语言中，为了获得相同的行为，你需要模拟懒惰。有些语言比其他语言更容易实现这一点，我更喜欢用erlang或F#来实现，而不是用C语言（尽管我知道C语言，但几乎不懂erlang或F# :)。在渴望的语言中，是否存在两个遍历取决于编译器。原则上，过滤器和映射可以融合，但通常需要编译器证明映射函数和过滤器谓词的纯净性才能实现。因此，在大多数情况下，我预计会有两次遍历，因为证明很难。 - Daniel Fischer

谢谢你，Daniel Fishcer。我永远感激 :) - Adi

对于感兴趣的人来说，Python的生成器主要存在是为了允许这种惰性处理。 - Marcin

同样地，许多Scala数据结构都提供了“.view”方法来允许这种惰性处理。 - Dan Burton