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! :)

Answer 1

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.

Answer 2

This is my approach for this (using Sets and comparing lengths)

import qualified Data.Set as Set -- From the 'containers' library

hasDuplicates :: (Ord a) => [a] -> Bool
hasDuplicates list = length list /= length set
  where set = Set.fromList list

I'm using the containers Haskell Package.

Answer 3

Try using nub.

import Data.List
hasDuplicates :: (Ord a) => [a] -> Bool
hasDuplicates xs = length (nub xs) /= length xs

Essentially, nub will return the unique elements of a list.