Resume a list without repeats

Question

Define a primitive recursive function capable of compressing the list by removing all elements repeated in sequence. Ex : aaabbbcddd abcd

Any idea how to do that? I honestly don’t know where to start.

Answer 1

I’m assuming this is the output you want.

• aaabbbcddd abcd
• aaabbbaaacddd abacd

For that you can try something like.

Version 1:

removeDups :: (Eq a) => [a] -> [a]
removeDups []             =  []
removeDups (xs : [])      =  [xs]
removeDups (x1:x2:xs)
          | x1 == x2     =      removeDups (x2 : xs)
          | otherwise    = x1 : removeDups (x2 : xs)

The following cases are trivial.

removeDups []             =  []    -- Lista vazia
removeDups (xs : [])      =  [xs]  -- Lista apenas com um elemento

The logic for the other cases is as follows:

• If two adjacent elements are equal then skip the first of the two elements and recursively evaluate the rest of the list until you find two different elements or find one of the trivial cases.
• If different then include the first element in the result list and evaluate the rest of the list recursively.

Version 2:

Alternative using only predefined functions

removeDups :: (Eq a) => [a] -> [a]
removeDups= map head . group

This version uses the function group which takes as a parameter a list and returns a list of lists in which each of the sub-lists is composed only of equal elements.

Function group

group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]

Then it’s simple, you apply the function head to each sub-list to return only the first.

If you want to get a list without repeating elements:

• aaabbbaaacddd abcd

Then just sort the list (using the function sort) before executing the function removeDups.

Answer 2

It’s been a while since you’ve been asked, but here goes my implementation.

removeDup :: String -> String
removeDup []     = []
removeDup [a]    = [a]
removeDup (x:xs) = x:(removeDup $ filter (/=x) xs)

Basically the magic happens when the filter removes the elements x of Xs

removeDup "abacabc"
-- 1º passo => 'a' : "bcbc"
-- 2º passo => 'a' : 'b' : "cc"
-- 3º passo => 'a' : 'b' : 'c' : [] == "abc"