我们公司的一些人正在阅读Haskell相关的内容，昨天我们谈论了一些概念。问题是，作为一种lazy（惰性）语言，Haskell如何处理检索列表中第n个元素？
比如说，如果我们有一个列表：
[2,4..10000000] !! 200
它会实际填充列表到200个元素吗？还是将其编译为类似于等式的形式？
n*step + firstValue
然后返回该计算结果？之所以会出现这种情况，是因为有人试图提供一个程序很容易耗尽内存的示例，而沿着（足够大的）列表向下遍历是首先想到的候选方案。
7个回答
12
是的，在返回结果之前，它将生成列表的前201个元素。但是，由于该列表在程序中无法从任何其他地方访问，因此随着程序执行，初始数据将被垃圾回收，因此它将使用恒定的空间（但是线性时间）进行原始实现。
当然，优化编译器可能会做得更好。由于您的表达式是常量，甚至可以在编译时对其进行计算。
- hammar
4
6但是要小心，如果列表生成不好，垃圾回收可能会受到阻碍。考虑
iterate (+2) 2 !! 10000000，每个列表元素都引用前一个元素，因此无法立即进行回收。 - Daniel Fischer@DanielFischer 一个严格版本的
iterate将在常量空间中运行。 - is7s1@is7s 当然，关键是列表开头的引用会防止垃圾收集。
iterate只是一个很容易创建这样引用的示例。 - Daniel Fischer3当心聪明的编译器的陷阱。据我所知，目前没有任何一个Haskell编译器能够比线性时间更好地优化这个表达式，而它在理论上可能存在并不能真正帮助。 - luqui
9
它是否会将列表填充到200个元素？
在一个朴素的实现中是这样的。
或者它是否会将其编译成类似于
n * step + firstValue的方程？
一种优化的Haskell编译器可能会这样做，但我不会期望实际的实现执行此优化。
关键是Haskell是如此严格规范化的，以至于可以证明这两个选项在理想化的机器上返回值相等，因此由编译器选择其中之一。语言标准（Haskell报告）只描述了应返回什么值，而不是如何计算。
- Fred Foo
7
术语“懒惰”在数学上有一个精确的含义，您可以从关于需求调用λ演算的书籍中了解。对于新手来说，“直到结果在其他地方需要时才评估任何内容”这个外行人的定义只是一个比喻。这是一种简化，因此在像这样的复杂情况下，需要理解完整理论以解释正在发生的事情。
精确的语义要求编译器不评估列表元素，直到对它们进行模式匹配。这不是优化问题 - 它必须始终如此。因此，如果计算a !! 3，则您最少会得到以下结果（它取决于a的定义）：
_ : _ : _ : 5 : _
这里的_表示“未评估”。您可以通过学习λ演算来了解什么被评估，什么没有被评估。在那之前，您可以使用GHCi调试器查看。
请注意，在打印x之前，l根本没有被评估。打印调用show函数，而show函数执行一系列模式匹配。在这个特定的情况下，由于[1..10]的实现中的模式匹配，列表的第一个元素得到评估（实际上它被转换为常规应用程序
根据程序的（静态已知！）结构，可能会发生许多情况。最少的时候，当你评估列表 !! 3，你会得到
精确的语义要求编译器不评估列表元素，直到对它们进行模式匹配。这不是优化问题 - 它必须始终如此。因此，如果计算a !! 3，则您最少会得到以下结果（它取决于a的定义）：
_ : _ : _ : 5 : _
这里的_表示“未评估”。您可以通过学习λ演算来了解什么被评估，什么没有被评估。在那之前，您可以使用GHCi调试器查看。
Prelude> let l = [1..10]
Prelude> let x = l !! 5
Prelude> :set -fprint-evld-with-show
Prelude> :print x
x = (_t1::Integer)
Prelude> :print l
l = (_t2::[Integer])
Prelude> x
6
Prelude> :print l
l = 1 : 2 : 3 : 4 : 5 : 6 : (_t3::[Integer])
请注意，在打印x之前，l根本没有被评估。打印调用show函数，而show函数执行一系列模式匹配。在这个特定的情况下，由于[1..10]的实现中的模式匹配，列表的第一个元素得到评估（实际上它被转换为常规应用程序
enumFromTo 1 10）。然而，如果我们添加m = map (+1) l，我们注意到更多的m元素未评估，因为map拥有比[1..10]更少的匹配模式：Prelude> let m = map (+1) l
Prelude> :print m
m = (_t4::[Integer])
Prelude> m !! 5
7
Prelude> :print m
m = (_t5::Integer) : (_t6::Integer) : (_t7::Integer) :
(_t8::Integer) : (_t9::Integer) : 7 : (_t10::[Integer])
我再次强调，很容易识别哪些内容被评估，哪些内容没有被评估，并且评估的顺序是什么，但您需要学习精确的语义 - 仅仅学习比喻并不能让您了解细节。最后一个例子是
> Prelude> let ll = zipWith (+) l (tail l) Prelude> ll !! 5 13 Prelude>
> :print l l = [1,2,3,4,5,6,7,8,9,10]
根据程序的（静态已知！）结构，可能会发生许多情况。最少的时候，当你评估列表 !! 3，你会得到
_ : _ : _ : 5 : _。最多的时候，你会得到完整的列表：1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : []。我可以很容易地构建这4个示例情况 - 所以你也可以学习，但需要一些数学背景。- nponeccop
1
+1！这个回答是我在Haskell中懒惰求值方面看到的最好的之一！ - Miguel
6
正如larsmans所说，这取决于编译器要做什么。但我期望 GHC 会填充列表直到第201个元素，但不会计算这些元素。
假设存在一个阶乘函数：
factorial n = product [1..n]
以下代码将打印200的阶乘，它将创建列表的前201个单元格，但只计算一个阶乘。
print $ [ factorial n | n <- [0,1..] ] !! 201
- jmg
6
取决于-Ox中的x。
在这个简单的情况下，GHC（7.0.2）确实足够聪明。
import Criterion.Main
import qualified Data.Vector as V
import qualified Data.List.Stream as S
naive _ = [2,4 .. k] !! n
eq _ = n*2 + 2
uvector _ = V.enumFromThenTo 2 4 k V.! n
stream _ = [2,4 .. k] S.!! n
n = 100000
k = 10*n
main = defaultMain [ bgroup "range"
[ bench "naive" $ whnf naive n
, bench "eq" $ whnf eq n
, bench "uvector" $ whnf uvector n
, bench "stream" $ whnf stream n
]]
-- -Odph -fforce-recomp -fllvm
--
--benchmarking range/naive
--mean: 11.83244 ns, lb 11.39379 ns, ub 12.90468 ns, ci 0.950
--std dev: 3.304705 ns, lb 1.189680 ns, ub 6.155017 ns, ci 0.950
--
--benchmarking range/eq
--mean: 7.911626 ns, lb 7.741035 ns, ub 8.122809 ns, ci 0.950
--std dev: 970.2263 ps, lb 828.3840 ps, ub 1.177933 ns, ci 0.950
--
--benchmarking range/uvector
--mean: 10.74393 ns, lb 10.30107 ns, ub 11.81737 ns, ci 0.950
--std dev: 3.268982 ns, lb 861.2390 ps, ub 5.811662 ns, ci 0.950
--
--benchmarking range/stream
--mean: 12.34206 ns, lb 11.71146 ns, ub 14.07016 ns, ci 0.950
--std dev: 4.959039 ns, lb 2.124692 ns, ub 10.40687 ns, ci 0.950
-- -O3 -fforce-recomp -fasm
--benchmarking range/naive
--mean: 11.11646 ns, lb 10.83341 ns, ub 11.82991 ns, ci 0.950
--std dev: 2.048823 ns, lb 289.9484 ps, ub 3.752569 ns, ci 0.950
--
--benchmarking range/eq
--mean: 8.535535 ns, lb 8.297940 ns, ub 9.067161 ns, ci 0.950
--std dev: 1.771753 ns, lb 933.7552 ps, ub 2.843637 ns, ci 0.950
--
--benchmarking range/uvector
--mean: 11.12599 ns, lb 10.88839 ns, ub 11.71998 ns, ci 0.950
--std dev: 1.734431 ns, lb 306.4149 ps, ub 3.123837 ns, ci 0.950
--
--benchmarking range/stream
--mean: 10.73798 ns, lb 10.42936 ns, ub 11.45102 ns, ci 0.950
--std dev: 2.301690 ns, lb 1.184686 ns, ub 3.877275 ns, ci 0.950
-- -O0 -fforce-recomp -fasm
--benchmarking range/naive
--mean: 1.742292 ms, lb 1.693402 ms, ub 1.934525 ms, ci 0.950
--std dev: 432.1991 us, lb 70.44581 us, ub 1.006263 ms, ci 0.950
--
--benchmarking range/eq
--mean: 37.66248 ns, lb 36.37912 ns, ub 42.66504 ns, ci 0.950
--std dev: 11.91135 ns, lb 1.493463 ns, ub 28.17839 ns, ci 0.950
--
--benchmarking range/uvector
--mean: 36.32181 ms, lb 35.41175 ms, ub 38.63195 ms, ci 0.950
--std dev: 6.887482 ms, lb 2.532232 ms, ub 13.47616 ms, ci 0.950
--
--benchmarking range/stream
--mean: 1.731072 ms, lb 1.692072 ms, ub 1.875080 ms, ci 0.950
--std dev: 342.2325 us, lb 81.77006 us, ub 792.2414 us, ci 0.950
在这个简单的情况下，GHC（7.0.2）确实足够聪明。
- klapaucius
1
2GHC的基础现在支持流，这就是为什么结果相似的原因。uvector在-O0下表现糟糕是预料之中的，因为它完全依赖于流来获得任何像样的性能。此外，您的评论表明您使用了uvector，但您的模块导入表明您使用了Vector。无论如何，查看Data.Vector.Unboxed的性能会很好。 - alternative
3
使用GHC，您可以编写类似以下的内容：
myVal = [2,4..] !! 200
该函数在无限列表中查找元素，因此它确实不会分配完整的列表。请参见http://www.haskell.org/haskellwiki/Memory_leak，了解Haskell中内存泄漏的示例。
- Simon Bergot
2
据我所知，所有实现都会根据需要填充列表。实际上，遍历足够大的列表很容易让你耗尽内存，你只需要安排好已经遍历过的部分不能被垃圾回收，例如：
main :: IO ()
main = do
let xs :: [Int]
xs = [1 .. 10^9]
print (xs !! 123456789)
print (xs !! 2)
将其编译为
fromIntegral n*step + start是一项棘手的任务，其有效性取决于类型。如果列表元素的类型是有界的，并且n足够大，则xs !! n将抛出"索引过大"异常，但算术运算可能是完全定义良好的。因此，该转换对于Integer是有效的，但并不普遍适用。- Daniel Fischer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
g k n m = sum . take k $ cycle [n,n+2..m]怎么样？这里也需要手动吗？ :) - Will Ness