CODEWITHSUNDEEP
listhaskellrecursion
T-Bird
T-Bird

Reputation: 187

Taking out the last occurrence of a certain element in a list in Haskell

I'm having trouble writing this function that takes a predicate and a list of integers, then eliminates the last occurrence of the integer that satisfies the predicate in the list. I was able to take out the first occurrence of the predicate in the list with my function below:

fun :: (Int -> Bool) -> [Int] -> [Int]
fun check (s:ss)
 |check s = ss
 |otherwise = s : fun check ss

What I need help on is how I should modify this function to take out the last occurrence of the integer, instead of the first. For example, fun (<2) [3,4,1,5,0,-3,9] would return [3,4,1,5,0,9].

Upvotes: 2

Views: 1860

Answers (3)

dfeuer
dfeuer

Reputation: 48631

If you want to have fun with it, try this version.

removeLast :: (a -> Bool) -> [a] -> [a]
removeLast p = fst . foldr go ([], False) where
  go x ~(r, more)
    | p x = (if more then x : r else r, True)
    | otherwise = (x : r, more)

This seems to be almost as lazy as it can be, and it gets to the point pretty quickly. It could produce the list spine more lazily with some effort, but it produces list elements maximally lazily.

After some more thought, I realize that there is some tension between different aspects of laziness in this case. Consider

removeLast p (x : xs)

There are two ways we can try to find out whether to produce a [] or (:) constructor.

  1. We can check xs; if xs is not [], then we can produce (:).

  2. We can check p x. If p x is False, then we can produce (:).

These are the only ways to do it, and their strictness is not comparable. The only "maximally lazy" approach would be to use parallelism to try it both ways, which is not the most practical approach.

Upvotes: 3

effectfully
effectfully

Reputation: 12735

(I couldn't use where due to some indentation problems)

removeLast :: (a -> Bool) -> [a] -> [a]
removeLast p xs =
    let
        go c  []    = tail (c [])
        go c (x:xs)
            | p x       = c (go (x:) xs)
            | otherwise = go (c . (x:)) xs
    in case break p xs of
        (ok, [])   -> ok
        (ok, x:xs) -> ok ++ go (x:) xs

go collects elements for which the predicate doesn't hold in a difference list and prepends this list to the result once a new satisfying the predicate element is found. Pattern matching on break p xs ensures that difference lists always start with an element that satisfies the predicate and we can drop it if it's the last.

Works with infinite lists:

main = do
    print $ removeLast (< 2) [3,4,1,5,0,-3,9]        -- [3,4,1,5,0,9]
    print $ removeLast (== 2) [1,3]                  -- [1,3]
    print $ take 10 $ removeLast (< 2) (cycle [1,3]) -- [1,3,1,3,1,3,1,3,1,3]

Here is an obfuscated version:

removeLast :: (a -> Bool) -> [a] -> [a]
removeLast p xs = case break p xs of
    (ok, [])   -> ok
    (ok, x:xs) -> ok ++ foldr step (tail . ($[])) xs (x:) where
        step x r c = if p x then c (r (x:)) else r (c . (x:))

Upvotes: 4

babon
babon

Reputation: 3774

How about this:

fun :: (Num a) => (a -> Bool) -> [a] -> [a]
fun check (s:ss)
    |check s = ss
    |otherwise = s : fun check ss

Then, apply your fun function like this:

reverse $ fun (\ x -> x `mod` 3 == 0) (reverse [1..10])

HTH

Upvotes: 0

Related Questions