CODEWITHSUNDEEP
listhaskellfunctional-programming
KScheer
KScheer

Reputation: 11

How to remove duplicate items in nested list?

I have a Haskel function called flatten that works as such:

flatten :: [[a]] -> [a] 
flatten []            = []
flatten ([]:vs)       = flatten vs
flatten ((x:xs):vs)   = x:flatten (xs:vs)

It takes a list of lists and combines it into one list. How can I make another function called flatten2set that works exactly like flatten (or calls flatten), but removes all duplicates, if any? I want to try and do this without tools like nub.

An example would be:

flatten2set [[1],[5,1,4],[9,1,3],[2,5]] --> [1,5,4,9,3,2]

I have attempted to implement a nub function:

nub:: Eq a => [a] -> [a]
nub (x:xs) = x : filter (/=x) (myNub xs)
nub [] = []

And when I have tried to use it like this:

flatten2set :: [[a]] -> [a]
flatten2set[x] = (myNub . flatten) [x]

I receive this error:

testing.hs:20:18: error:

• No instance for (Eq a) arising from a use of ‘myNub’
  Possible fix:
    add (Eq a) to the context of
      the type signature for:
        flatten2set :: forall a. [[a]] -> [a]
• In the first argument of ‘(.)’, namely ‘myNub’
  In the expression: myNub . flatten
  In the expression: (myNub . flatten) [x]

Any help would be appreciated!

Upvotes: 1

Views: 416

Answers (1)

Silvio Mayolo
Silvio Mayolo

Reputation: 70277

You have an excellent implementation of myNub

myNub :: Eq a => [a] -> [a]
myNub (x:xs) = x : filter (/=x) (myNub xs)
myNub [] = []

Then you try to call it

flatten2set :: [[a]] -> [a]
flatten2set = myNub . flatten

But you've declared that flatten2set works for any a. The compiler is simply pointing out that that cannot be. What if we tried to call flatten2set with a list of lists of functions? It won't work because myNub requires Eq and functions are not comparable. Since we call a function that requires Eq a, we too must require Eq a.

flatten2set :: Eq a => [[a]] -> [a]
flatten2set = myNub . flatten

I took the liberty of removing the [x], which had no purpose. If you really want to have an argument, you just name the argument. There's no need to pattern match on it.

flatten2set :: Eq a => [[a]] -> [a]
flatten2set x = (myNub . flatten) x

Using [x] is an assertion that, in this case, the list will contain exactly one element, and we want flatten2set to work on lists containing any number of elements.

Upvotes: 3

Related Questions