Haskell-filter first element

Question

I want to remove the first element that does not have a certain property. For example, if my property is defined as...

greaterOne :: Num a=>Ord a=>a->Bool
greaterOne x = x > 1

Then the function filterFirst should give me this...

filterFirst greaterOne [5,-6,-7,9,10]
>> [5,-7,9,10]  //removes first element that is not greater than one

This is my attempt...

filterFirst :: (a->Bool)->[a]->[a]
filterFirst p [] = []
filterFirst p (x:y:xs)
    |p x = filterFirst p xs
    |otherwise = y:xs

Can someone help me out?

You probably want something like `f p xs = let (as, (b:bs)) = span p xs in as ++ bs`, possibly with some logic to handle the cases where no element matches the predicate and where the last element is the first to match. — genisage, Mar 06 '15 at 00:59
`filterFirst p (x:xs) = if p x then x : filterFirst p xs else xs` — user2407038, Mar 06 '15 at 01:16

Chad Groft · Accepted Answer · 2015-03-06T22:18:41.090

Walk through what your attempt does: [] is sent to [] (this is correct). With a list with at least two elements (x:y:xs), your function tests x, throws out x and y and keeps filtering if the test passes (definitely not what you want), and throws out x and stops if the test fails (this is correct). A list with a single element errors out, as will many other lists with an odd number of elements (this is both bad and a clue to the correct answer).

Let's walk through a correct implementation a step at a time. As you wrote, we want filterFirst to take a predicate on a and a list of a and return another list of a:

filterFirst :: (a -> Bool) -> [a] -> [a]

The predicate type a -> Bool can't be broken down, but [a] can: there can be empty lists [] and nonempty lists x:xs, and there should be a case for each:

filterFirst p []     = ...
filterFirst p (x:xs) = ...

In the "base case" [], there's nothing left to filter, so we want this to be [], which is what you've written. Since p isn't used here, you could replace p in this case with _:

filterFirst _ [] = []

but you don't have to.

What we want to do with x:xs depends on the value of p x. If p x holds, we want a list that starts with x. The tail of this list should be xs, but with the first failing element removed. If p x fails, we want to throw out x (the first failing element) and keep xs (the list after the first failing element). So:

filterFirst p (x:xs)
    | p x       = x:filterFirst p xs
    | otherwise = xs

And that covers all the possibilities, so we're done!

EDIT per dfeuer's comment.

Great answer, but I would write "If `p x` holds" rather than "If `p x == True`". A lot of people get confused and write funny-looking code using `==` to test `Bool` values. — dfeuer, Mar 06 '15 at 19:35

score 5 · Answer 2 · answered Mar 06 '15 at 02:52

5

You can abuse deleteBy for this.

> deleteBy (>) 1 [5, -6, -7, 9, 10]
[5,-7,9,10]

...and more generally:

filterFirst p = deleteBy (const p) undefined

answered Mar 06 '15 at 02:52

Daniel Wagner

145,880
9
220
380

Haskell-filter first element

2 Answers2

Linked