0
我不明白爲什麼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
在什麼情況下輸入類型可以從輸出不同?
謝謝,
塞巴斯蒂安。
我不明白爲什麼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
在什麼情況下輸入類型可以從輸出不同?
謝謝,
塞巴斯蒂安。
在任何情況下,這裏暗示:該函數是無用的。
這實際上是「免費定理」的一個很好的例子。很明顯,Ord t => [t] -> [a]
這個類型沒有多大意義,因爲只能生成[a]
類型的列表(你對a
不瞭解)是空列表。因此,這證明了q
只能做兩件事情:
[]
⟂
)事實上前者是發生了什麼:在每個遞歸步驟,你彈出關閉輸入列表中的某個元素,但實際上從未在結果中包含任何這些元素。所以你總是以[]
結束。
如果要正確實現快速排序,你當然帶來x
兩個子列表之間的背部,即
q (x:xs) = q us ++ [x] ++ q ws
如果你試圖解決這個實施列表會發生什麼?這種類型有一個很好的理由。嘗試執行'q [1,3,2]',你能告訴我爲什麼你得到那個輸出嗎? – bheklilr
少數情況下,忽略簽名實際上導致錯誤的有用提示,而不是一個更令人困惑的錯誤! – leftaroundabout
@bheklilr對於輸出爲[]的任何輸入,該輸出是因爲在每一步中,您都會刪除輸入的第一個元素。 – Fof