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
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.
6
I’m assuming this is the output you want.
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:
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:
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"
Browser other questions tagged haskell
You are not signed in. Login or sign up in order to post.
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).
– BrunoRB
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
– Rigotti