我正在查看 stackoverflow Non-Trivial Lazy Evaluation，这让我看到了 Keegan McAllister 的演讲：为什么要学习 Haskell。在幻灯片 8 中，他展示了最小函数，定义为：
minimum = head . sort
并声明其复杂度为 O(n)。如果按替换排序为 O(nlog n)，我不明白为什么说复杂性是线性的。帖子中提到的排序不能是线性的，因为它不对数据进行任何假设，因为线性排序方法（例如计数排序）需要它。
懒惰的评估在这里起到了神秘的作用吗？如果是这样，背后的解释是什么？
在minimum = head . sort中，sort不会完全完成，因为它不会预先完成。sort只会根据head.
在例如合并排序中，首先n将列表的数字成对比较，然后将获胜者配对并比较（n/2数字），然后是新的获胜者（n/4），等等。总而言之，O(n)比较以产生最小元素。
mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
where
pairs (x:y:t) = merge x y : pairs t
pairs xs = xs
merge (x:xs) (y:ys) | less y x = y : merge (x:xs) ys
| otherwise = x : merge xs (y:ys)
merge xs [] = xs
merge [] ys = ys
可以对上面的代码进行扩充，以标记它产生的每个数字，并在其生产中进行一些比较：
mgsort xs = go $ map ((,) 0) xs where
go [] = []
go xs = head $ until (null.tail) pairs [[x] | x <- xs] where
....
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (a+c+1,d) : merge ((a+1,b):xs) ys -- cumulative
| otherwise = (a+c+1,b) : merge xs ((c+1,d):ys) -- cost
....
g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]] -- a little scrambler
运行它几个列表长度，我们看到它确实是~ n：
*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]
要查看排序代码本身是否为~ n log n，我们对其进行更改，以便每个生成的数字仅携带其自身的成本，然后通过对整个排序列表求和来找到总成本：
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (c+1,d) : merge ((a+1,b):xs) ys -- individual
| otherwise = (a+1,b) : merge xs ((c+1,d):ys) -- cost
以下是各种长度列表的结果，
*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]
*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]
上面显示了随着列表长度增加的经验增长顺序，n如通常通过~ n log n计算所展示的那样迅速减少。另请参阅此博客文章。这是一个快速的相关性检查：
*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in
map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]
编辑：惰性评估可以比喻为一种生产者/消费者习语1，以独立的记忆存储作为中介。我们编写的任何生产性定义都定义了一个生产者，该生产者将在其消费者要求时，一点一点地生产其输出 - 但不会更快。无论生产什么都被记忆，因此如果另一个消费者以不同的速度消费相同的输出，它会访问相同的存储空间，之前已填充。
当没有更多的消费者引用一个存储时，它会被垃圾收集。有时，通过优化编译器能够完全取消中间存储，从而将中间人排除在外。
1另见：Oleg Kiselyov、Simon Peyton-Jones 和 Amr Sabry 的Simple Generators v. Lazy Evaluation 。
假设minimum' :: (Ord a) => [a] -> (a, [a])是一个函数，它返回列表中的最小元素以及删除该元素的列表。显然，这可以在 O(n) 时间内完成。如果你然后定义sort为
sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
where
(xmin, xs') = minimum' xs
那么惰性求值意味着(head . sort) xs只计算第一个元素。如您所见，此元素只是 pair 的（第一个元素）minimum' xs，它是在 O(n) 时间内计算的。
当然，正如 delnan 指出的那样，复杂性取决于sort.
您已经获得了大量解决head . sort. 我将添加一些更一般的陈述。
通过热切评估，各种算法的计算复杂性以一种简单的方式构成。例如， 的最小上界 (LUB)f . g必须是 和 的LUB 之f和g。因此，您可以将f和g视为黑盒并仅根据其 LUB 进行推理。
然而，通过惰性求值，f . gLUB 可以比 和 的 LUB 之f和更好g。您不能使用黑盒推理来证明 LUB；您必须分析实现及其交互。
因此，经常被引用的事实是惰性求值的复杂性比急切求值更难推理。想想以下。假设您正在尝试提高一段代码的渐近性能，其形式为f . g. 在急切的语言中，您可以遵循明显的策略来执行此操作：选择更复杂的fand g，然后先改进它。如果你成功了，你就成功了f . g。
另一方面，在惰性语言中，您可能会遇到以下情况：
fand g，但f . g没有改进（甚至变得更糟）。f . g以无济于事（甚至恶化）f或g.解释取决于 的实现sort，而对于某些实现，这将是不正确的。例如，对于在列表末尾插入的插入排序，惰性求值没有帮助。因此，让我们选择一个实现来查看，为了简单起见，让我们使用选择排序：
sort [] = []
sort (x:xs) = m : sort (delete m (x:xs))
where m = foldl (\x y -> if x < y then x else y) x xs
该函数显然使用 O(n^2) 时间对列表进行排序，但由于head只需要列表的第一个元素，sort (delete x xs)因此永远不会评估！
它没有那么神秘。您需要对列表的多少进行排序才能提供第一个元素？您需要找到最小元素，这可以在线性时间内轻松完成。sort碰巧的是，惰性求值的某些实现会为您执行此操作。
在实践中看到这一点的一种有趣方式是跟踪比较函数。
import Debug.Trace
import Data.List
myCmp x y = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare x y
xs = [5,8,1,3,0,54,2,5,2,98,7]
main = do
print "Sorting entire list"
print $ sortBy myCmp xs
print "Head of sorted list"
print $ head $ sortBy myCmp xs
首先，注意整个列表的输出与跟踪消息交错的方式。其次，请注意仅计算头部时跟踪消息的相似之处。
我刚刚通过 Ghci 运行了这个，它并不完全是 O(n)：需要 15 次比较才能找到第一个元素，而不是应该需要的 10 次。但它仍然小于 O(n log n)。
编辑：正如 Vitus 在下面指出的那样，进行 15 次比较而不是 10 次与说它不是 O(n) 不同。我的意思是它需要超过理论最小值。
受保罗约翰逊回答的启发，我绘制了这两个函数的增长率。首先，我修改了他的代码，每次比较打印一个字符：
import System.Random
import Debug.Trace
import Data.List
import System.Environment
rs n = do
gen <- newStdGen
let ns = randoms gen :: [Int]
return $ take n ns
cmp1 x y = trace "*" $ compare x y
cmp2 x y = trace "#" $ compare x y
main = do
n <- fmap (read . (!!0)) getArgs
xs <- rs n
print "Sorting entire list"
print $ sortBy cmp1 xs
print "Head of sorted list"
print $ head $ sortBy cmp2 xs
计算*和#字符，我们可以在均匀间隔的点对比较计数进行采样（请原谅我的 python）：
import matplotlib.pyplot as plt
import numpy as np
import envoy
res = []
x = range(10,500000,10000)
for i in x:
r = envoy.run('./sortCount %i' % i)
res.append((r.std_err.count('*'), r.std_err.count('#')))
plt.plot(x, map(lambda x:x[0], res), label="sort")
plt.plot(x, map(lambda x:x[1], res), label="minimum")
plt.plot(x, x*np.log2(x), label="n*log(n)")
plt.plot(x, x, label="n")
plt.legend()
plt.show()
运行脚本将为我们提供以下图表：
下线的斜率是..
>>> import numpy as np
>>> np.polyfit(x, map(lambda x:x[1], res), deg=1)
array([ 1.41324057, -17.7512292 ])
..1.41324057（假设它是一个线性函数）