在Haskell中总结无限列表的一部分

Question

我对下面的例子中Haskell执行的确切方式感到有些困惑

sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

在这里查找所有奇数方格是小于总和的代码10000 ,我知道如何将这些takewhile,filter,map职能的工作.我的疑问是,这里的map函数是从无限列表中取一个元素并将其平方并将平方元素列表返回给filter函数吧？在这种情况下,它将无限运行,以便无限的元素列表不是吗？或者它只采取一个元素平方,然后返回filter？

Answer 1

Haskell尽可能地懒惰.它不计算你没有要求它的任何值,如果你这样做,let nums = filter odd (map (^2) [1..])你还没有强迫它计算任何东西.现在它知道它nums是类型的Num a => [a](因为你描述的操作的类型),但它不知道任何关于它的东西(这很好!)

即使你跑步,takeWhile (<10000)你也不会强迫任何数字.现在ghc知道takeWhile (<10000) nums有类型(Ord a, Num a) => [a](你在比较时引入了额外的类型类(<)),但这就是它所知道的.

即使你打电话sum,ghc也不必做任何事情.sum期待一个Num a => [a](技术上是一个(Num a, Foldable t) => t a但是让我们假装现在这些是同样的事情)并且你已经给了它一个.直到你实际要求该操作的结果,ghc 什么都不做.您可以通过let foobar = sum [1..]在解释器中进行测试.只要你没有要求结果foobar,Haskell就可以使用那个表达式了.

但是,如果你曾经要求这个结果,你就强迫整行计算.sum需要它的列表,所以它要求takeWhile (<10000)它.takeWhile需要它的列表,所以它要求filter odd它.filter需要它的列表,所以它要求map (^2)它,但一次filter不需要整个列表,所以map仍然尽可能懒惰,并一次给每个数字.

一旦takeWhile找到一个数字(>=10000),它就不再需要了,并且愉快地交给sum你,这会产生你的结果并且ghc又回到了懒惰状态,nums除非你需要它们,否则不会再产生任何结果.