CODEWITHSUNDEEP
setsmlset-intersectionset-difference
Le Coder
Le Coder

Reputation: 79

SML set difference

I have to implement set union, difference and intersection. However when insert extremely nested sets with tuples it gives me the wrong answer. I have included the code snippet for the functions. Any suggestion I could do to improve my output? 

val x17 = {1, 2, 8};
val x18 = {{1, 2, 8}, (1, {1, 2, 8})};
val x19 = ({{1, 2, 8}, (1, {1, 2, 8})}, {1, 2, 8});

example operations:

x20 = {x19} Union x18;
x21 = x20 \ {x17};
x22 = x20 intersection {x17};

correct answer:

x20 ={{1, 2, 8}, (1, {1, 2, 8}), ({{1, 2, 8}, (1, {1, 2, 8})}, {1, 2, 8})};
x21 ={(1, {1, 2, 8}), ({{1, 2, 8}, (1, {1, 2, 8})}, {1, 2, 8})};
x22 ={{1, 2, 8}};

my output:

let x20 be {{1,2,8},(1,{1,2,8})};
let x21 be {(1,{1,2,8})};
let x22 be {{1,2,8}};

code

 datatype expression = SET of expression list | INT of int 
     fun interFunc (SET [],SET b,interSet) = SET (rev interSet)
        | interFunc (SET a,SET [],interSet) = SET (rev interSet)
        | interFunc (SET (h1::t1),SET b,interSet) = if (List.exists (fn x=>x=h1) b) then interFunc(SET t1,SET b,h1::interSet) else interFunc(SET t1,SET b,interSet);

      fun garbage [] = []
        | garbage (h::t) = if (List.exists (fn x=>x=h) t) then h::(garbage t) else (garbage t);

      fun unionFunc (SET [],SET b) = SET (b)
        | unionFunc (SET a,SET []) = SET (a)
        | unionFunc (SET a,SET b) = SET (garbage a@b);


      (* set operation: difference, modified interFunc *)
      fun diffFunc (SET [],SET b,diffSet) = SET (rev diffSet)
        | diffFunc (a,SET [],diffSet) = SET (rev diffSet)
        | diffFunc (SET (h1::t1),SET b,diffSet) = if (List.exists (fn x=>x=h1) b) then diffFunc(SET t1,SET b,diffSet) else diffFunc(SET t1,SET b,h1::diffSet);

Upvotes: 1

Views: 988

Answers (1)

ruakh
ruakh

Reputation: 183351

Offhand, I see a few bugs:

garbage (h::t) = if (List.exists (fn x=>x=h) t) then h::(garbage t) else (garbage t)

It looks like garbage is intended to remove duplicates by selecting the last occurrence of each value; for example, given [1,2,3,2,1,2], it should return [3,1,2]. However, what it actually does is discard the last occurrence of each value, so it would give [1,2,2] instead.

diffFunc (SET (h1::t1),SET b,diffSet) = if (List.exists (fn x=>x=h1) b) then diffFunc(SET t1,SET b,diffSet) else diffFunc(SET t1,SET b,h1::diffSet);

If h1 occurs in b, then you need to do something to filter that out of b. The above doesn't do that, so in essence it produces the union rather than the symmetric difference.

Overall, I recommend reading Eric Lippert's blog post "How to debug small programs" for general advice on debugging your program.

Upvotes: 2

Related Questions