CODEWITHSUNDEEP
haskell
Erakura
Erakura

Reputation: 35

Iterating through list in reverse

Assume the following (non-functioning) code, that takes a predicate such as (==2) and a list of integers, and drops only the last element of the list that satisfies the predicate:

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

This code does not work, so clearly lists cannot be iterated through in reverse like this. How could I implement this idea? I'm not 100% sure if the code is otherwise correct - but hopefully it gets the idea across.

Upvotes: 0

Views: 599

Answers (2)

Alec
Alec

Reputation: 32309

Borrowing heavily from myself: the problem with this sort of question is that you don't know which element to remove until you get to the end of the list. Once we observe this, the most straightforward thing to do is traverse the list one way then back using foldr (the second traversal comes from the fact foldr is not tail-recursive).

The cleanest solution I can think of is to rebuild the list on the way back up, dropping the first element.

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)

The return type is Either to differentiate between not found anything to drop from the list (Left), and having encountered and dropped the last satisfying element from the list (Right). Of course, if you don't care about whether you dropped or didn't drop an element, you can drop that information:

 cutLast' f = either id id . cutLast f

Following the discussion of speed in the comments, I tried swapping out Either [a] [a] for (Bool,[a]). Without any further tweaking, this is (as @dfeuer predicted) consistently a bit slower (on the order of 10%).

Using irrefutable patterns on the tuple, we can indeed avoid forcing the whole output (as per @chi's suggestion), which makes this much faster for lazily querying the output. This is the code for that:

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)

However, this is 2 to 3 times slower than either of the other two versions (that don't use irrefutable patterns) when forced to normal form.

Upvotes: 3

chepner
chepner

Reputation: 531055

One simple (but less efficient) solution is to implement cutFirst in a similar fashion to filter, then reverse the input to and output from that function.

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

Upvotes: 2

Related Questions