CODEWITHSUNDEEP
haskellrecursionduplicates
Zappa89
Zappa89

Reputation: 11

Creating a function using subset language Core Haskell to remove duplicate items in a list

The language I'm using is a subset of Haskell called Core Haskell which does not allow the use of the built-in functions of Haskell. For example, if I were to create a function which counts the number of times that the item x appears in the list xs, then I would write:

count = \x -> 
            \xs -> if null xs 
                     then 0
                     else if x == head xs 
                            then 1 + count x(tail xs) 
                            else count x(tail xs)

I'm trying to create a function which outputs a list xs with its duplicate values removed. E.g. remdups (7:7:7:4:5:7:4:4:[]) => (7:4:5:[])

can anyone offer any advice?

Thanks!

Upvotes: 1

Views: 466

Answers (2)

Lay González
Lay González

Reputation: 2985

This works with Ints:

removeDuplicates :: [Int] -> [Int]
removeDuplicates = foldr insertIfNotMember []
           where
            insertIfNotMember item list = if (notMember item list)
                          then item : list
                          else list

notMember :: Int -> [Int] -> Bool
notMember item [] = True
notMember item (x:xs)
          | item == x = False 
          | otherwise = notMember item xs

How it works should be obvious. The only "tricky" part is that the type of foldr is:

(a -> b -> b) -> b -> [a] -> b

but in this case b unifies with [a], so it becomes:

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

and therefore, you can pass the function insertIfNotMember, which is of type:

Int -> [Int] -> [Int]   -- a unifies with Int

Upvotes: 1

mhwombat
mhwombat

Reputation: 8136

I'm guessing that you're a student, and this is a homework problem, so I'll give you part of the answer and let you finish it. In order to write remdups, it would be useful to have a function that tells us if a list contains an element. We can do that using recursion. When using recursion, start by asking yourself what the "base case", or simplest possible case is. Well, when the list is empty, then obviously the answer is False (no matter what the character is). So now, what if the list isn't empty? We can check if the first character in the list is a match. If it is, then we know that the answer is True. Otherwise, we need to check the rest of the list -- which we do by calling the function again.

elem _ []       = False
elem x (y:ys)   = if x==y
                    then True
                    else elem x ys

The underscore (_) simply means "I'm not going to use this variable, so I won't even bother to give it a name." That can be written more succinctly as:

elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

Writing remdups is a little tricky, but I suspect your teacher gave you some hints. One way to approach it is to imagine we're partway through processing the list. We have part of the list that hasn't been processed yet, and part of the list that has been processed (and doesn't contain any duplicates). Suppose we had a function called remdupHelper, which takes those two arguments, called remaining and finished. It would look at the first character in remaining, and return a different result depending on whether or not that character is in finished. (That result could call remdupHelper recursively). Can you write remdupHelper?

remdupHelper = ???

Once you have remdupHelper, you're ready to write remdups. It just invokes remdupHelper in the initial condition, where none of the list has been processed yet:

remdups l = remdupHelper l []             -- '

Upvotes: 2

Related Questions