CODEWITHSUNDEEP
haskell
buydadip
buydadip

Reputation: 9417

Haskell-filter first element

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?

Upvotes: 7

Views: 4284

Answers (2)

Chad Groft
Chad Groft

Reputation: 380

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.

Upvotes: 8

Daniel Wagner
Daniel Wagner

Reputation: 152707

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

Upvotes: 5

Related Questions