如何模式匹配列表的結尾？

Question

說我想在列表的末尾刪除所有零：

removeEndingZeros :: (Num a, Eq a) => [a] -> [a] 
removeEndingZeros (xs ++ [0]) = removeEndingZeros xs 
removeEndingZeros xs   = xs 

這不，因爲在參數中(++)運營商的合作。我如何通過模式匹配來確定列表的結尾？

Answer 1

有在Data.List一個函數來做到這一點：

dropWhileEnd :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x : xs) [] 

所以，你可以用

dropWhileEnd (== 0) 

---

下降的尾隨零

另一個非常相似，功能可以實現這樣的：

dropWhileEnd2 :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd2 p = foldr (\x xs -> if null xs && p x then [] else x : xs) [] 

dropWhileEnd2 p具有完全相同的語義reverse . dropWhile p . reverse，但可以合理地預期常數因子要快。 dropWhileEnd與其他人有不同的，不可比較的嚴格性（在某些方面它更嚴格，其他方面更嚴格）。

你能弄清楚在什麼情況下每一種情況都可以預計會更快？

Answer 2

在標準的Haskell中，你不能在列表的末尾模式匹配。由於定義了列表的方式，因此訪問列表的末尾需要時間與列表的長度成線性關係。既然你不能沒有在最壞的情況下兩次遍歷下降尾隨零，明顯的解決方案是好的 - 從列表中的反向下降前導零，然後再反向恢復原來的秩序：

removeEndingZeros = reverse . dropWhile (== 0) . reverse