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

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.


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.


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.

Tags:

Haskell