手冊推導

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