Как шаблон сопоставить конец списка?

Question

Скажите, что я хотел, чтобы удалить все нули в конце списка:

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

Это не работает из-за (++) оператора в аргументе. Как определить конец списка с помощью сопоставления с образцом?

Answer 1

Eсти функция в 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