Haskell如何处理列表？

Question

我们中的一些人正在阅读有关Haskell的一些内容,我们昨天正在讨论一些概念.问题是Haskell是一种懒惰的语言,它如何处理检索列表的第n个元素？

例如,如果我们有

 [2,4..10000000] !! 200

它实际上是否会将列表填充到200个元素中？或者它将其编译成类似于的等式

n*step + firstValue

然后返回那个计算？出现这种情况的原因是有人试图想出一个程序很容易耗尽内存的例子,并且想到遍历一个(足够大)的列表是第一个出现的候选人.

Answer 1

是的,它会在返回之前产生列表的前201个元素.但是,由于此列表无法从程序中的任何其他位置访问,因此初始位将有资格进行垃圾收集,因此它将以一个简单的实现在恒定空间(但线性时间)内运行.

当然,优化编译器可能会做得更好.由于表达式是常量,因此甚至可以在编译时对其进行求值.

Answer 2

它实际上是否会将列表填充到200个元素中？

在一个天真的实现中,是的.

或者它是否将其编译成类似于n*step + firstValue？的等式？

优化的Haskell编译器可能会这样做,但我不希望实际的实现执行此优化.

关键是Haskell是如此严格地形式化,以至于可以证明这两个选项在理想化机器上的返回值方面是等价的,因此编译器可以选择其中一个.语言标准(Haskell报告)只描述了应返回的值,而不是应该如何计算.

Answer 3

"懒惰"一词具有精确的数学意义,你可以通过需要lambda演算的书籍来学习.外行人的定义"在其他地方需要结果之前,没有任何评估"只是新手的隐喻.这是一种简化,所以在这种复杂的情况下,需要理解完整的理论来解释正在发生的事情.

精确语义要求编译器在执行模式匹配之前不评估列表元素.这不是优化的问题 - 它总是必须如此.所以,如果你计算一个!! 3,你得到的最小值(取决于a的定义)如下:

_:_:_:5:_

_在这里_我的意思是"未评估".通过学习lambda演算,您可以学习理解评估的内容和不评估的内容.在此之前,您可以使用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个样本情况 - 所以你也可以学习,但它需要一些数学背景.

Answer 4

正如larsmans所说,由编译器来决定做什么.但我希望GHC能够填充这个列表直到第201个元素.但它不会评估这些元素.

假设有一个阶乘函数:

factorial n = product [1..n]

以下代码将打印200的阶乘,它将创建列表的前201个单元格,但它将仅评估一个阶乘.

print $ [ factorial n | n <- [0,1..] ] !! 201

Answer 5

它取决于-Ox中的x

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)确实非常聪明.