Haskell function that tests if a list has repeated (duplicate) elements

Question

I have an exercise to do, however and since I'm new to the language, I can not find any way on how to do it.

I have this function "repeated" that's defined as such, given under this paragraph. It receives a list of Int and gives back a Bool value. It's supposed to check if a list has any repeated elements. If so, it's TRUE, if not, it's false. There is one extra: I have to define the function by recursion, so it has to be a recursive function. Would appreciate any help.

repeated :: [Int] -> Bool

EDIT1: So far, I've only managed to succeed with this amount of code

repeated :: [Int] -> Bool
repeated [] = False
repeated (h:t) =

Which gives me back the empty list, only. The rest, I've not been able to figure out so far...

EDIT2: Forgot about the singular lists... Also, possible answer?

repeated :: [Int] -> Bool
repeated [] = False
repeated [_] = False
repeated (h:t) = if elem h t then True
                             else repeated t

That's pretty much it. I've compiled the .hs and it worked perfectly. Thank you all for the suggestions and hints! :)

It's probably easier to just use nub: repeated xs = xs == nub xs? — Bakuriu
It depends if it's 'repeated' elements or 'duplicate' elements. I would read 'repeated' as being 'elements next to each other which are the same', and 'duplicate' as 'elements anywhere in the list which are the same'. Repeated is the same problem as an arbitrary list of Ord a which has been sorted. — Matthew Walton
As a side note, I would like to point out that this was a superb SO question. You had a specific problem to solve, you participated in discussion promptly, edited your question to be more appropriate and for clarity, and added code as you started to solve the problem from hints. — bheklilr

bheklilr bheklilr · Accepted Answer · 2014-10-06T14:22:40

You want to find if a list has any duplicates. This means that you'll have to keep up with a list of elements that you've already visited so you can check this. So first, write a function that checks if a single element exists in a list of already visited values:

alreadyVisited :: Int -> [Int] -> Bool
alreadyVisited x [] = False
alreadyVisited x (v:visited) = ???

(Note: this is known as elem in Prelude, but you should be able to implement it yourself, and it's good practice)

Then you'll want to write the main function that loops over all elements in your target list, building a set of visited elements until it finds a duplicate. Once a duplicate is found, the function can exit without checking the rest of the list.

-- Using a helper hides the fact that the visited list is needed
repeated :: [Int] -> Bool
repeated xs = go xs []
--                   ^--  initial visited list is empty
    where
        -- same base case that you came up with,
        -- an empty list does not have duplicate elements
        go [] _ = False
        -- The recursive step, think about what you need this function to do
        go (x:xs) visited =
            if alreadyVisited x visited
                then ???        -- If it's already visited, do what?
                else ???        -- Otherwise?

Here I've just set up the structure for you, you'll have to fill in the details yourself. Keep in mind that this is not an efficient implementation, particularly because of how slow alreadyVisited will become as visited grows in size, but if you are interested in speed then you can swap out the visited list for a Data.Set.Set, which has much better lookup time.

Haskell function that tests if a list has repeated (duplicate) elements

3 Answers