Find If Duplicates Exist SML NJ
I want to write one function that searches for a list and finds if the list contains duplicate values. The function must return a boolean value. This is where I am, but it doesn't work ...
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
thank!
source to share
As @Marcin explained in a comment, a simple and efficient way is to use a duplicate checker set. SML / NJ has many sets of structures available in the Utility Library .
As far as your function is concerned, you cannot compare x
and myFunc xs
, as they may not be of the same type. And an empty list is a non-duplicate list ( myFunc []
should return false
).
It works:
fun duplicated [] = false
| duplicated (x::xs) = (List.exists (fn y => x = y) xs) orelse (duplicated xs)
However, the worst time complexity is O (n 2 ) (which n
is the length of the list), which is quite inefficient.
source to share