Search code examples
listhaskellfold

own nub function - how to use foldl/foldr?


Here is my own implementation of nub (remove duplicates):

nub :: (Eq a) => [a] -> [a]
nub lista = nub_rec lista []
    where
        nub_rec :: (Eq a) => [a] -> [a] -> [a]
        nub_rec [] acc = acc
        nub_rec (x:xs) acc = nub_rec (filter (\y -> if y == x then False else True) xs) (x:acc)

I consider how to use foldr/foldl to implement nub, could you help me ? I can't see a way.


Solution

  • First, your implementation of nub is bit more complex than it needs to be (and it reverses the order of elements in the list). Here's a simpler one:

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

    Now, if we want to use foldr to write a function that will output, not just an "aggregate" but a full list, it's useful to first have a look at the simplest foldr-based function that takes in a list and spits out a list:

    myNoop :: [a] -> [a]
    myNoop l = foldr (\ x xs -> x : xs) [] l
    

    Given that, the filter must be inserted somewhere. Since I assume this is a homework, I'll leave that to the OP as an exercise :)