Learning Haskell: How to remove an item from a List in Haskell

Question

Trying to learn Haskell. I am trying to write a simple function to remove a number from a list without using built-in function (delete...I think). For the sake of simplicity, let's assume that the input parameter is an Integer and the list is an Integer list. Here is the code I have, Please tell me what's wrong with the following code

areTheySame :: Int -> Int-> [Int]

areTheySame x y | x == y = []
                | otherwise = [y]

removeItem :: Int -> [Int] -> [Int]

removeItem x (y:ys) = areTheySame x y : removeItem x ys

Answer 1

The : operator doesn't do what you think it does:

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

It takes an item of type a and adds it to the beginning of a list of type a. You're using it to join two lists of type a. For that, you need to use ++:

(++) :: [a] -> [a] -> [a]

Also, if you make a recursive function, it needs an ending condition. So try this:

removeItem _ [] = []
removeItem x (y:ys) = areTheySame x y ++ removeItem x ys

That way, when you get to the end of the list, the function will stop recursing.

Answer 2

This is the minimal fix to make your example work:

removeItem :: Int -> [Int] -> [Int]
removeItem _ []     = []
removeItem x (y:ys) = areTheySame x y ++ removeItem x ys

First, you need to use ++ to concatenate lists, as the : operator used by you adds just one element to the beginning of a list (it can neither be used to add lists with one element nor to add empty lists). You first compare the head of the list (y) to the item you want to remove and correctly return the item or an empty list using areTheySame. Then you want to recursively continue using removeItem on the rest of the list (ys). The resulting list needs to be concatenated using ++.

Second, as Chris Lutz noted, you need an ending condition when you reach the end of the list. By adding this line, Haskell knows what to do with an empty list (that is, nothing, just return an empty list).

As Chuck said, you can simplify the code for this task by having removeItem not delegate the task of the comparison, but compare itself and throw away the element if it should be removed, otherwise keep it at the list head (using :). In any case, continue recursively with the rest of the list.

-- nothing can be removed from an empty list
-- ==> return empty list and stop recursion
removeItem _ []     = []

-- if the list is not empty, cut off the head in y and keep the rest in ys
--                    if x==y, remove y and continue
removeItem x (y:ys) | x == y    = removeItem x ys    
--                    otherwise, add y back and continue 
                    | otherwise = y : removeItem x ys

Answer 3

The others are right that the problem is the : operator. I would say that your areTheySame function that returns a list is the wrong approach anyway, though. Rather than switch to the ++ operator, a better implementation of that function would be:

removeItem _ []                 = []
removeItem x (y:ys) | x == y    = removeItem x ys
                    | otherwise = y : removeItem x ys

As you can see, this is a pretty simple implementation. Also, consing like this is much less taxing for your program than appending a bunch of lists together. It has other benefits as well, such as working lazily.

Answer 4

For reference, you may be interested in seeing how it's done in delete from Data.List.

You could leave areTheySame as is, but you'd then need to use concatMap in removeItem to collapse the empty lists:

removeItem :: Int -> [Int] -> [Int]
removeItem x xs = concatMap (areTheySame x) xs

or equivalently

removeItem :: Int -> [Int] -> [Int]
removeItem x = concatMap (areTheySame x)

Note that the types of your functions could be more general:

areTheySame :: (Eq a) => a -> a -> [a]
removeItem  :: (Eq a) => a -> [a] -> [a]

This allows removal of items from lists of any type for which == is defined, not just Int.

Answer 5

You can also do this as a list-comprehension

delete :: Eq a => a -> [a] -> [a]
delete deleted xs = [ x | x <- xs, x /= deleted ]

Answer 6

I believe all the solutions given so far work differently than Data.List.delete, which only deletes the first member.

deleteFromList x xs =
  case break (==x) xs of
    (_,[]) -> xs
    (notsat,sat) -> notsat ++ tail sat

was my attempt to delete only the first member (haven't peaked at D.L yet).

It's unclear which behavior the top poster wants.