Remove first element that fulfills predicate (Haskell)

Question

I want to make a function that removes the first element that fulfills the predicate given in the second argument. Something like this:

removeFirst "abab" (< 'b')  = "bab"
removeFirst "abab" (== 'b') = "aab"
removeFirst "abab" (> 'b')  = "abab"
removeFirst [1,2,3,4] even  = [1,3,4]

I wanted to do it by recursively, and came up with this:

removeFirst :: [a] -> (a -> Bool) -> [a]
removeFirst [] _ = []
rremoveFirst (x:xs) p = if p x then x : removeFirst xs p else removeFirst xs p

(Inspired by this question) But I get a type-error, like this:

Couldn't match type ‘a’ with ‘Bool’
  Expected: [Bool]
    Actual: [a]
  ‘a’ is a rigid type variable bound by
    the type signature for:
      removeFirst :: forall a. [a] -> (a -> Bool) -> [a]

or this:

ghci> removeFirst [1,2,3,4] even

<interactive>:25:1: error:
    * Variable not in scope: removeFirst :: [a0] -> (a1 -> Bool) -> t
    * Perhaps you meant `rem' (imported from Prelude)

I know this is a relatively simple thing to program, I am just not familiar enough with Haskell yet. How can I do this "Haskell-style" (in one line)?

Answer 1

Before doing it "in style", why not first simply do it, so it works. This is how we learn.

"Variable not in scope: removeFirst ..." simply means you haven't defined the function named removeFirst.

So it seems you first tried to define it (and the error you show does not go with the code you show), then you got errors so it didn't get defined, and then you tried calling it and got the error saying it's not defined yet, naturally.

So, save your program in a source file, then load that file in GHCi. Then if you get any errors please copy-paste the full code from your file into your question (do not re-type it by hand). Also please specify what is it you do when you get the error messages, precisely. And be sure to include the error messages in full by copy-pasting them as well.

Then the logic of your code can be addressed.

---

Since others have posted working code, here's how I'd code this as a one-liner of sorts:

remFirst :: [a] -> (a -> Bool) -> [a]
remFirst xs p = foldr g z xs xs
  where
  g x r ~(_:tl)      -- "r" for recursive result
     | p x           -- we've found it, then
       = tl          -- just return the tail
     | otherwise
       = x : r tl    -- keep x and continue
  z _  = []          -- none were found

Shortened, it becomes

remFirst xs p = 
  foldr (\x r ~(_:tl) -> if p x then tl else x : r tl)
        (const []) xs xs

Answer 2

Not one line, but it works.

 removeFirst :: [a] -> (a -> Bool) -> [a]
 removeFirst (x:xs) pred
   | pred x    = xs
   | otherwise = x : removeFirst xs pred

For a one-liner, I imagine you'd want to use foldl to walk across the list from the left.

EDIT

This solution uses guards, it first checks to see if the first element of the list passed in satisfies the predicate, and if not, it prepends it to the list and recursively checks the tail of the passed in list.

Answer 3

Using manual recursion does not lead to a one-liner solution, so let's try using some pre-built recursion scheme from the library.

Function scanl :: (b -> a -> b) -> b -> [a] -> [b] looks handy. It produces a succession of states, one state per input item.

Testing under the ghci interpreter:

$ ghci
 λ> 
 λ> p = (=='b')
 λ> 
 λ> xs = "ababcdab"
 λ> ss = tail $ scanl (\(s,n) x -> if (p x) then (x,n+1) else (x,n)) (undefined,0)  xs
 λ> 
 λ> ss
 [('a',0),('b',1),('a',1),('b',2),('c',2),('d',2),('a',2),('b',3)]
 λ> 

At that point, it is easy to spot and get rid of the one unwanted element, thru some simple data massaging:

 λ> 
 λ> filter (\(x,n) -> (n /= 1) || (not $ p x))  ss 
 [('a',0),('a',1),('b',2),('c',2),('d',2),('a',2),('b',3)]
 λ> 
 λ> map fst $ filter (\(x,n) -> (n /= 1) || (not $ p x))  ss 
 "aabcdab"
 λ> 

Let's now write our removeFirst function. I take the liberty to have the predicate as leftmost argument; this is what all library functions do.

removeFirst :: (a -> Bool) -> [a] -> [a]
removeFirst p =
    let
        stepFn = \(s,n) x -> if (p x) then (x,n+1) else (x,n)
        p2     = \(x,n) -> (n /= 1) || (not $ p x)
    in
        map fst . filter p2 . tail . scanl stepFn (undefined,0)

If required, this version can be changed into a one-liner solution, just by expanding the values of stepFn and p2 into the last line. Left as an exercise for the reader. It makes for a long line, so it is debatable whether that improves readability.

Addendum:

Another approach consists in trying to find a library function, similar to splitAt :: Int -> [a] -> ([a], [a]) but taking a predicate instead of the list position.

So we submit the (a -> Bool) -> [a] -> ([a],[a]) type signature into the Hoogle specialized search engine.

This readily finds the break library function. It is exactly what we require.

 λ> 
 λ> break (=='b') "zqababcdefab"
 ("zqa","babcdefab")
 λ> 

So we can write our removeFirst function like this:

removeFirst :: (a -> Bool) -> [a] -> [a]
removeFirst p xs = let  (ys,zs) = break p xs  in  ys ++ (tail zs)

The source code for break simply uses manual recursion.