Retract a list without repeating them

1

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

Any ideas how to do this? I honestly do not know where to start.

    
asked by anonymous 25.05.2015 / 00:41

2 answers

5

I'm assuming this is the output you want.

  • aaabbbcddd → abcd
  • aaabbbaaacddd → abacd

For this you can try something like this.

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 the first of the two elements jumps and recursively evaluates the rest of the list until you find two different elements or find one of the trivial cases.
  • If they are different then include the first element in the result list and evaluate the rest of the list recursively.

Version 2:

Alternative that uses only predefined functions

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

This version uses the group function that receives a list as a parameter and returns a list of lists where each of the sub-lists is made up of equal elements.

Function group

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

Then it's simple, you apply the head function to each of the sublists to return only the first element.

If you want to get a list without repeated elements:

  • aaabbbaaacddd → abcd

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

    
26.05.2015 / 15:21
3

It's been a while since I've been asked, but here's my implementation.

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

Basically magic happens when the filter removes the xs elements from xs

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