Week 7: Explanation for exercise 6.1 (Symmetric Difference of Lists)

Subsite home page:  http://bit.ly/focs-aux

Exercise 6.1

Implement the function diff which computes the symmetric difference of two lists, which means collecting all of the elements that appear only in one of the lists. The order of the remaining elements should stay unchanged. Remember we are interested in collecting elements that appear exactly in one of the lists. In particular, elements that appear in both lists l1 and l2 should not be in diff l1 l2 .

Example:

l1 = [1;2;3;2;3]

l2 = [3;4;3]

diff l1 l2 = [1;2;2;4]

We do this exercise in three steps:

First step:

First we define a function called subdif that takes a list and an entry and returns a list with all elements different than the given entry

subdif: 'a list -> 'a -> 'a list

Let’s see how subdif works

subdif [1;2;3;2;3] 3 =
1 :: subdif [2;3;2;3] 3 =
1 :: 2 :: subdif [3;2;3] 3 =
1 :: 2 :: subdif [2;3] 3 =
1 :: 2 :: 2 :: subdif [3] 3 =
1 :: 2 :: 2 :: [] =
[1;2;2]

And this is how we define the function subdif

Let rec subdif l ent = match l with
                      | [] -> []
                      | x :: xs ->
                        if (x = ent) then subdif xs ent
                        else x :: subdif xs ent

Second step:

In the second step, we define another function which we call prediff. We expect this function to take two lists l1 and l2 and return all of elements in l1 which are not in l2. Note that this function is not symmetric with respect to the two lists l1 and l2. So, this cannot be our final answer.

The type of this function would then be

predif: 'a list -> ' a list -> 'a list

And the function itself is

Let rec predif l1 l2 = match l2 with
                   | [] -> l1
                   | x ::xs -> predif (subdif l1 x) xs ;;

Now let’s look at some computation done with the function we just defined

predif [1;2;3;2;3] [3;4;3] =
predif (subdif [1;2;3;2;3] 3) [4;3] =
predif [1;2;2] [4;3] =
predif (subdif [1;2;2] 4) [3] =
predif ([1;2;2]) [3] =
predif (subdif [1;2;2] 3) [] =
predif [1;2;2] [] =
[1;2;2]

Final step:

Now finally we can define symmetric difference function diff.

It has the type

diff: 'a list -> 'a list -> 'a list

And the function itself

Let rec subdif l ent = match l with
                    | [] -> []
                    | x :: xs ->
                      if (x = ent) then subdif xs ent
                      else x :: subdif xs ent


Let rec predif l1 l2 = match l2 with
                    | [] -> l1
                    | x ::xs -> predif (subdif l1 x) xs



Let rec diff l1 l2 = append (predif l1 l2) (predif l2 l1) ;;

A set theoretical remark:

It’s hard to not notice that our definition of symmetric difference of lists is analogous to of symmetric difference of sets, except that the case of sets is even simpler because we don’t care about maintaining the order while we are taking the difference.

In other words, since sets do not have order structure, there is nothing to be checked about order preservation.

For symmetric difference of sets look at: https://en.wikipedia.org/wiki/Symmetric_difference

A different and shorter solution:

Remark: There is a library function val filter which you might find useful in order to come up with another solution for this exercise:

val filter : ('a -> bool) -> 'a list -> 'a list

filter p l returns all the elements of the list l that satisfy the predicate p. The order of the elements in the input list is preserved.

The following function computes symmetric difference

let predif xs ys = filter (fun x -> not (mem x ys)) xs

where

val mem : 'a -> 'a list -> bool
mem a l is true if and only if a is equal to an element of l.