Resume a list without repeats

Asked

Viewed 2,119 times

2

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.

2 answers

6


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.

3

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"
  • 2

    Solves the problem, but see that it is a quadratic implementation (O(n 2)), for each element you go through the whole list looking if it is not there, practically a Bubble Sort of the removal of duplicates (but will an upvote for the simplicity of the function).

  • True, but it seems to me that you don’t have much to do. nub (method that does the same thing) from Data.List does something very similar. http://hackage.haskell.org/package/base-4.8.2.0/docs/src/Data.OldList.html#nub

Browser other questions tagged

You are not signed in. Login or sign up in order to post.