How to terminate an array modification function in haskell?

sloorush 0
Viewed 90

So I have this function...

removeDuplicate :: [CustomType] -> [CustomType]
removeDuplicate [] = []
removeDuplicate [x] = [x]
removeDuplicate [x, y] = 
    if x==y then [x]
    else [x, y]
removeDuplicate (x:y:xs) = 
    if x==y
        then removeDuplicate ([x] ++ xs)
    else removeDuplicate ([y] ++ xs ++ [x])

Here, I have to check if there is an element in the array(sorted) which is equal to other elements in the array.

I am unable to work on a termination condition for this function. It just goes into an infinite loop over here.

Normally, I could have used a visited array or count for this kind of situation but I'm new to Haskell and I am not sure what is the way to handle this situation.

P.S. Please let me know if any other details are needed.

haskell
1 Answers

removeDuplicate ([y] ++ xs ++ [x]) does not reduce the size of the array, and will thus eventually keep cycling the list. Indeed, if you have a list [1,2,4], it wll be called with removeDuplicate [1,2,4], then removeDuplicate [2,4,1] and then removeDuplicate [4,1,2] and thus again removeDuplicate [1,2,4], this will keep repeating itself.

You should ensure that you each time work on a smaller list. This can here be done by just emitting the

removeDuplicate :: Eq a => [a] -> [a]
removeDuplicate [] = []
removeDuplicate [x] = [x]
removeDuplicate (x:xs@(y:_))
    | x == y = removeDuplicate xs
    | otherwise = x : removeDuplicate xs

This will only filter out duplicates if these are "neighbors", you thus can for example sort the list as a pre-processing step.

If you want to handle lists where the duplicates can occur at any location, you should work with an accumulator that keeps track of the already seen items:

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = go []
    where go _ [] = []
          go seen (x:xs)
               | x `elem` seen = …
               | otherwise = …

where I leave implementing the … parts as an exercise.

Willem Van Onsem0
Related