CODEWITHSUNDEEP
haskell
zhong zheng
zhong zheng

Reputation: 25

Haskell: How to remove a List from a List in Haskell

I have a first list and a second list, and I want to write a function that takes two lists and returns a list containing only those elements in the second list that do not appear in the first. And I don't want to use built-in functions. For example:

> removeAll [1..3] [0..10]
[0,4,5,6,7,8,9,10]

> removeAll "aeiou" "supercalifragilisticexpialidocious"
"sprclfrglstcxpldcs"

removeAll _ [] = [] 
removeAll [] y = y

removeAll (x:xs) (y:ys)
    | x==y = removeAll xs ys
    | otherwise = y:removeAll xs ys

Upvotes: 0

Views: 953

Answers (3)

Yongwei Wu
Yongwei Wu

Reputation: 5582

A problem of your current code is that you tried to recurse in two lists simultaneously in one function. You need to divide and conquer. If elem is allowed, you may write:

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

If you do not want to use the built-in elem as well, you can define it similarly:

myElem :: Eq a => a -> [a] -> Bool
myElem _ [] = False
myElem x (y:ys)
    | x == y = True
    | otherwise = myElem x ys

Upvotes: 0

lsmor
lsmor

Reputation: 5063

There is a pretty straightforward recursive definition

removeAll :: Eq a => [a] -> [a] -> [a]
removeAll _        []     = []
removeAll toRemove (x:xs) 
  | x `belongs` toRemove = removeAll toRemove xs 
  | otherwise            = x:removeAll toRemove xs 
    where belongs _ [] = False
          belongs a (y:ys)
            | a == y    = True
            | otherwise = belongs a ys

The belongs function is just the prelude defined elem. Since you don't want to use built-in functions you have to define it yourself.

Upvotes: 0

Mateen Ulhaq
Mateen Ulhaq

Reputation: 27201

This is one simple way:

removeAll ignores = filter (\x -> notElem x ignores)

which makes use of:

If you wanted to write it in "pure-pure" Haskell, with no auxiliary functions... well, it sounds like it would be pretty ugly since we'd need to do some sort of nested for-loop. Here's a compromise:

myFilter _ [] = []
myFilter pred (x:xs)
  | pred x = x : myFilter pred xs
  | otherwise = myFilter pred xs

myNotElem e [] = True
myNotElem e (x:xs)
  | e == x = False
  | otherwise = myNotElem e xs

removeAll ignores = myFilter (\x -> myNotElem x ignores)

Upvotes: 1

Related Questions