CODEWITHSUNDEEP
listhaskell
demathieu
demathieu

Reputation: 489

Function that removes element if it exists but adds it of it does not

I'm looking for a cleaner way to write a function that adds an element to a list if the list does not contain it. Or otherwise removes it if the list does contain it, I'm using an if clause now and the function is working.

But I'm trying to find a more haskell-ish way to right this.

This is my code: 

removeElemOrAdd :: Eq a => a -> [a] -> [a]
removeElemOrAdd elem list = if (List.elem elem list)
                            then (filter(\x -> x /= elem) list)
                            else (elem:list)

Upvotes: 2

Views: 176

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 153102

I like the other approaches, but don't like that they behave differently than the specification. So here is an approach that:

  1. Like the original, deletes all copies, if there are any, AND
  2. like the original, inserts the new value at the beginning, if necessary, BUT
  3. unlike the original, uses a clever trick based on the ideas of beautiful folding (and follow-up developments) to make only one pass through the data.

The basic idea is that we will have a single value which tracks both whether all values so far have been a mismatch as well as the resulting filtered list. The injectNE operation will perform this operation for a single element of the list, and we will then use foldMap to expand from one element to the whole input list.

import Data.Monoid

injectNE :: Eq a => a -> a -> (All, [a])
injectNE old new = (All ne, [new | ne]) where
    ne = old /= new

removeElemOrAdd :: Eq a => a -> [a] -> [a]
removeElemOrAdd x xs = case foldMap (injectNE x) xs of
    (All nex, noxs) -> [x | nex] ++ noxs

In the final pattern, you should read nex as "no element was equal to x", and noxs as "the list without any copies of x" (get it? "no xs"? ba-dum-tsh).

It is slightly unfortunate that the spec was written the way it was, though: in particular, one of the selling points of beautiful folding is that its resulting one-pass folds can be friendlier to the garbage collector. But the spec makes that quite hard, because we must traverse the entire input list before deciding what the first element of the result list should be. We can improve the friendliness to the garbage collector significantly by relaxing point (2) above (but leaving (1) and (3)); and moreover the difference is merely swapping the arguments to (++), a nicely semantic diff to see in your revision history:

-- <snipped identical code>
removeElemOrAdd x xs = case ... of
    ... -> noxs ++ [x | nex]

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477230

Note: a small ambiguity in your question is what to do when x already occurs multiple times in the original list. I assumed this won't happen and in case it does, only the first occurrence is removed. Meaning that removeElemOrAdd 2 [4,2,5,2,7] will result in [4,5,2,7]. Furthermore it is unspecified where the item should be added. Because it has some advantages, I've opted to do this at the end of the list.

An implementation without using any library methods is the following:

removeElemOrAdd :: Eq a => a -> [a] -> [a]
removeElemOrAdd x (y:ys) | x == y = ys
                         | otherwise = y : removeElemOrAdd x ys
removeElemOrAdd x _ = [x]

Or a shorter version:

removeElemOrAdd :: Eq a => a -> [a] -> [a]
removeElemOrAdd x = reoa
    where reoa (y:ys) | x == y = ys
                      | otherwise = y : reoa ys
          reoa _ = [x]

or an equivalent implementation (see discussion below):

removeElemOrAdd :: Eq a => a -> [a] -> [a]
removeElemOrAdd x = reoa
    where reoa (y:ys) | x == y = ys
                      | otherwise = y : reoa ys
          reoa [] = [x]

The function works as follows: in case we are talking about a list with at least one item (y:ys), we compare x with y and if they are equal, we return ys: in that case we have removed the element and we are done.

Now in case the two are not equal, we return a list construction (:) with y in the head since we need to retain y and in the tail, we will do a recursive call removeElemOrAdd with x and ys. Indeed: it is possible that there is an x somewhere in the tail ys to remove, and furthermore we still need to add x to the list if it does not occur.

That clause will loop recursively through the list. From the moment it finds an y such that x == y it will remove that y. It is however possible that we reach the end of the list, and still have not found the element. In that case we will call the final clause. Here we know the list is empty (we could have written removeElemOrAdd x []) but to make the function definition syntactically total, I have opted to use an underscore. We can only reach this state if we have failed to find x in the list, so then we add it to the tail of the list by returning [x].

An advantage of this approach over using the if-then-else is that this does all tasks at once (checking, removing and adding) making it more efficient.

Another advantage is that this can run on an "infinite" list (like for instance the list of prime numbers). The list is evaluated lazily, so if you want to take the first three items, this function will only check the equality of the first three items.

Upvotes: 5

dfeuer
dfeuer

Reputation: 48611

I'd use a fold to remove all copies:

removeOrAdd x xs = foldr go (bool [x] []) xs False where
  go y r found
    | y == x = r True
    | otherwise = y : r found

To remove just one, a paramorphism seems to be in order:

removeOrAdd x = para go [x] where
  go y ys r
    | y == x = ys
    | otherwise = y : r

Upvotes: 0

Related Questions