我明白那个：
head (map (2**) [1..999999])
实际上只会评估 2**1，其余的都不会，但我正在阅读的书说：
head (sort somelist)
只需要在列表中找到最小的项目，因为这就是全部使用的。这是如何运作的？据我所知，这对于我知道的排序算法（如冒泡排序）是不可能的。
我认为这可行的唯一方法是，如果排序算法要遍历整个列表以寻找最小的项目，然后在没有该项目的情况下在列表上递归。对我来说，这听起来很慢。
这是排序功能的工作原理，还是有另一种我不知道的排序算法可以允许短路？
这：
只需要在列表中找到最小的项目，因为这就是全部使用的。
...真的应该说该函数只需要完成排序算法找到最小元素所需的最少工作量。
例如，如果我们使用快速排序作为我们的底层排序算法，则head . quicksort相当于称为“快速选择”的最佳（！）选择算法，这是最坏情况下的线性。此外，我们可以仅通过 来实现k -quickselect 。take k . quicksort
维基百科在其关于选择算法的文章中指出（我的重点）：
由于对排序的语言支持更为普遍，因此在许多环境中首选排序和索引的简单方法，尽管它在速度方面存在劣势。实际上，对于惰性语言，如果您的排序足够惰性，这种简单化的方法甚至可以为 k 最小/最大排序（最大/最小值作为特例）获得最佳复杂度。
快速排序在这种情况下工作得很好，而 Haskell 中的默认排序（合并排序）的组合不太好，因为它所做的工作比返回排序列表的每个元素所必需的要多。正如Haskell 邮件列表中的这篇文章所指出的：
惰性快速排序能够产生前 k 个最小元素的批次
O(n + k log k) 总时间 [1]
而懒惰的归并排序需要
O(n + k log n) 总时间 [2]
有关更多信息，您可能想阅读这篇博文。
如果您创建一个跟踪其参数的比较函数，例如在 GHCi 的命令行中：
> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y
然后您可以自己查看行为：
> sortBy myCompare "foobar"
" Cmp 'f' 'o'
Cmp 'o' 'b'
Cmp 'f' 'b'
Cmp 'a' 'r'
Cmp 'b' 'a'
a Cmp 'b' 'r'
b Cmp 'f' 'o'
Cmp 'f' 'r'
f Cmp 'o' 'o'
Cmp 'o' 'r'
o Cmp 'o' 'r'
or"
Haskell 正在懒惰地评估字符串，一次一个字符。找到每个字符时打印左列，右列记录所需的比较，如“trace”打印。
请注意，如果您编译它，尤其是在优化的情况下，您可能会得到不同的结果。优化器运行一个严格分析器，它可能会注意到整个字符串都被打印出来了，所以急切地评估它会更有效。
然后尝试
> head $ sortBy myCompare "foobar"
Cmp 'f' 'o'
Cmp 'o' 'b'
Cmp 'f' 'b'
Cmp 'a' 'r'
Cmp 'b' 'a'
'a'
如果您想了解这是如何工作的，请查看 sort 函数的源代码并在纸上手动评估“sort "foobar"”。
qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
where (less, greater) = partition (< x) xs
所以
qsort ('f':"oobar")
= qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
= ("a" ++ "b") ++ "f" ++ qsort ('o':"or")
现在我们已经做了足够的工作来发现“a”是结果中的第一项，而无需评估对“qsort”的其他调用。我省略了实际比较，因为它隐藏在对“分区”的调用中。实际上“分区”也是惰性的，所以事实上，就我所展示的而言，另一个“qsort”的参数还没有被评估过。
您刚才描述的算法有一个特定的名称：“选择排序”。这是 O(n 2 ) 所以它不是你能做的最快的事情。但是，如果您想要排序数组中的第一个“k”元素，那么复杂度将是 O(kn)，如果“k”足够小（如您的示例），这很好。
请注意，您正在使用函数式语言中的纯函数。sort通过查看函数的组合方式，编译器很可能能够为这两种情况生成优化的代码。它可以很容易地推断出您在撰写时想要的最小元素head和sort.