Find if Duplicates Exist SML NJ

Go To StackoverFlow.com

3

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!

2012-04-05 17:28
by MCR
You realise that SML/NJ supports sets - Marcin 2012-04-05 17:41
you mean use fold or find - MCR 2012-04-05 18:08
No, I mean that you can use the set to detect whether your list contains duplicates - Marcin 2012-04-05 18:24


9

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(n2) (n is the length of the list) which is quite inefficient.

2012-04-05 18:46
by pad
I actually just figured the problem out and this is exactly what I did. Thank you - MCR 2012-04-05 18:49
Why not a set-based solution, out of interest - Marcin 2012-04-06 06:31
Sometimes I'm thinking that there should be a penalty tax on writing redundant conditionals like if ... then true else ... : - Andreas Rossberg 2012-04-06 15:59
@AndreasRossberg: I hope that the penalty is as small as one more edit :) - pad 2012-04-06 16:04
Ads