Find if Duplicates Exist SML NJ

Question

I want to write a single function that searches a list and finds if there are any duplicates values in this list. The function should return a boolean. Here is where I'm at, but this is not working...

fun myFunc [] = true
myFunc(x::xs) = 
if(x=myFunc(xs)) then false
else myFunc(xs);

[1,2,2,3,4,5,6] should return true
[1,2,3,4,5,6,7] should return false
[1,2,3,4,5,6,1] should return true

thanks!

Answer 1

As @Marcin said in the comment, an easy and efficient way is to use set for checking duplication. SML/NJ have many set structures available in Utility Library.

Regarding your function, you cannot compare x and myFunc xs since they may not have the same type. And empty list is a list without duplication (myFunc [] should return false).

This works:

fun duplicated [] = false
  | duplicated (x::xs) = (List.exists (fn y => x = y) xs) orelse (duplicated xs)

However, the worst-case time complexity is O(n²) (n is the length of the list) which is quite inefficient.