Итерации по списку в обратном

Question

Предположим следующее (нефункционирующих) код, который принимает предикат, такие как (==2) и список целых чисел, и падает только последний элемент списка, который удовлетворяет предикат:

cutLast :: (a -> Bool) -> [Int] -> [Int] 
cutLast a [] = [] 
cutLast pred (as:a) 
| (pred) a == False = (cutLast pred as):a 
| otherwise   = as 

Этот код не работает, поэтому четкие списки не могут быть повторены в обратном порядке. Как я мог реализовать эту идею? Я не уверен на 100%, если код в противном случае правилен, но, надеюсь, он передумает.

Answer 1

Одним простым (но менее эффективным) решением является реализация cutFirst по аналогии с filter, а затем обратный ввод и вывод этой функции.

cutLast pred = reverse . cutFirst . reverse 
    where cutFirst [] = [] 
     cutFirst (x:xs) | pred x = xs 
         | otherwise = x : cutFirst xs 

Answer 2

Заимствование в значительной степени от myself: проблема с таким вопросом заключается в том, что вы не знаете, какой элемент удалить, пока не дойдете до конца списка. Как только мы это наблюдаем, самое прямолинейное дело - переместить список в один конец, затем обратно, используя foldr (второй обход происходит из-за того, что foldr не является хвостовым рекурсивным).

Чистое решение, о котором я могу думать, состоит в том, чтобы перестроить список на пути назад, отбросив первый элемент.

cutLast :: Eq a => (a -> Bool) -> [a] -> Either [a] [a] 
cutLast f = foldr go (Left []) 
    where 
     go x (Right xs) = Right (x:xs) 
     go x (Left xs) | f x = Right xs 
         | otherwise = Left (x:xs) 

Возвращаемый тип Either различать что-либо отказаться от списка (Left) не найдено, и встретив и бросил последний удовлетворительный элемент из списка (Right). Конечно, если вы не заботитесь о упали ли вы или не уронить элемент, вы можете оставить эту информацию:

cutLast' f = either id id . cutLast f 

---

После обсуждения скорости в комментариях, я попытался выгрузив Either [a] [a] для (Bool,[a]). Без какой-либо дополнительной настройки это (как прогнозировалось @dfeuer) последовательно немного медленнее (порядка 10%).

Используя неопровержимые шаблоны на кортеже, мы действительно можем избежать форсирования всего вывода (согласно предложению @ chi), что делает это намного быстрее для ленивого запроса вывода. Это код, который:

cutLast' :: Eq a => (a -> Bool) -> [a] -> (Bool,[a]) 
cutLast' f = foldr go (False,[]) 
    where 
     go x ~(b,xs) | not (f x) = (b,x:xs) 
        | not b = (False,x:xs) 
        | otherwise = (True,xs) 

Однако это от 2 до 3 раз медленнее, чем любой из двух других версий (которые не используют Неопровержимые) при вынужденных к нормальной форме.