手册推导

Question

我不明白为什么q的类型是Ord t => [t] -> [a]而不是Ord a => [a] -> [a]

q [] = [] 
q (x:xs) = q us ++ q ws 
    where us = filter (<=x) xs 
     ws = filter (>=x) xs 

在什么情况下输入类型可以从输出不同？

谢谢，
塞巴斯蒂安。

Answer 1

在任何情况下，这里暗示：该函数是无用的。

这实际上是“免费定理”的一个很好的例子。很明显，Ord t => [t] -> [a]这个类型没有多大意义，因为只能生成[a]类型的列表（你对a不了解）是空列表。因此，这证明了q只能做两件事情：

• 返回[]
• 不会终止（即⟂）

事实上前者是发生了什么：在每个递归步骤，你弹出关闭输入列表中的某个元素，但实际上从未在结果中包含任何这些元素。所以你总是以[]结束。

如果要正确实现快速排序，你当然带来x两个子列表之间的背部，即

q (x:xs) = q us ++ [x] ++ q ws