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

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