Comp 110 Difference

Difference

The difference of two sets is the set of all elements of A that are not also elements of B. Another way to think of it is A - (A ∩ B). 

The difference of sets A and B can be depicted with a venn diagram. 

Examples

1. A = {1, 2, 3, 4}, B = {3, 4}

           A - B = {1, 2}

2. A = {1, 2, 3, 4}, B = {1, 2, 3, 4}

            A - B = { }

            A - B is equal to the empty set because A = B.

3. A = {1, 2, 3, 4}, B = {5, 6, 7, 8}

            A - B = {1, 2, 3, 4}

            In this case, A - B = A because A and B have no overlap.

Implementing a difference function

Here is how the difference of two data sets may be implemented in code! If you are fuzzy on generic functions, check out this page.

let difference = <T> (a: List<T>, b: List<T>): List<T> => {
    if (a === null) {
        return null;
    } else if (includes(b, first(a))) {
        return difference(rest(a), b);
    } else {
        return cons(first(a), difference(rest(a), b));
    }
};
let includes = <T> (a: List<T>, item: T): boolean => {
    if (a === null) {
        return false;
    } else if (first(a) === item) {
        return true;
    } else {
        return includes(rest(a), item);
    }
};
let main = async () => {
    let listA: List<number> = cons(1, cons(2, cons(3, cons(4, null))));
    let listB: List<number> = cons(3, cons(4, null));
    print(difference(listA, listB));
};
main();

This difference function takes in two Lists of the same type, and returns a list containing the elements which do not overlap. This function is very similar to the union function that was implemented as a hands-on in Lecture 10! 

Note than when we call the function in main we put listA as the first argument and listB as the second. This results in A - B being processed. All we would have to do to get B - A would be to reverse the order of the arguments:  difference(listB, listA).