CODEWITHSUNDEEP
listhaskell
AnchovyLegend
AnchovyLegend

Reputation: 12538

Removing the first instance of x from a list

I am new to Haskell and have been trying to pick up the basics.

Assume I have the following list y:

3:3:2:1:9:7:3:[]

I am trying to find a way to delete the first occurrence of 3 in list y. Is this possible using simple list comprehension?

What I tried (this method deletes all instances from a list):

deleteFirst _ [] = [] 
deleteFirst a (b:bc) | a == b    = deleteFirst a bc 
                     | otherwise = b : deleteFirst a bc

Upvotes: 3

Views: 8562

Answers (4)

Luis Casillas
Luis Casillas

Reputation: 30227

sepp2k's remarks about list comprehensions are an important thing to understand; list operations like map, filter, foldr and so on treat all list items uniformly, and the important thing to understand about them is what information is available at each step, and how each step's result is combined with those of other steps.

But the aspect I want to stress is that I think you should really be trying to solve these problems in terms of library functions. Adapting the solution from this older answer of mine to your problem:

deleteFirst x xs = beforeX ++ afterX
    -- Split the list into two pieces:
    --   * prefix = all items before first x
    --   * suffix = all items after first x
    where (beforeX, xAndLater) = break (/=x) xs
          afterX = case xAndLater of
                     [] -> []
                     (_:xs) -> xs

The trick is that break already has the "up to first hit" behavior built in it. As a further exercise, you can try writing your own version of break; it's always instructive to learn how to write these small, generic and reusable functions.

Upvotes: 0

David Unric
David Unric

Reputation: 7719

as other already mentioned list comprehension is not an appropriate solution to this task (difficult to terminate the execution at one step).

You've almost written the correct solution, just in the case of equality with the matched value you had to terminate the computation by returning the rest of list without the matched element:

deleteFirst _ [] = [] 
deleteFirst a (b:bc) | a == b    = bc 
                     | otherwise = b : deleteFirst a bc

> print $ deleteFirst 3 (3:3:2:1:9:7:3:[])
> [3,2,1,9,7,3]

Upvotes: 4

sepp2k
sepp2k

Reputation: 370112

No, it's not possible using a list comprehension. In a list comprehension you make a decision which element to keep based on that element only. In your example, you want to treat the first 3 you encounter differently than other 3s (because you only want to remove the first one), so the decision does not depend on the element alone. So a list comprehension won't work.

Your attempt using a recursive function is already pretty close, except that, as you said, it removes all instances. Why does it remove all instances? Because after you removed the first one, you call deleteFirst again on the rest of the list, which will remove the next instance and so on. To fix this, just do not call deleteFirst again after removing the first instance. So just use bc instead of deleteFirst a bc in that case.

Upvotes: 6

Joachim Breitner
Joachim Breitner

Reputation: 25763

I don’t believe it is possible to do this with list comprehension (at least not in in any idiomatic way).

Your deleteFirst works almost. All you need to change to fix is is to stop deleting after the first match, i.e. replace deleteFirst a bc in the first clause by bc.

Upvotes: 2

Related Questions