Homework 6 Solution

Problem 1: weaving triplets

If any of the three input lists are empty, then stop weaving. Otherwise, create a triplet (a three element list) from the first elements of your input lists and cons the triplet onto the rest of the result.

Problem 2a: is this a set?

Our input is a set if either:

Problem 2b: make a set

Making a set from an empty list is easy, just return the empty list. If our list is non-empty:
  1. make a set from the list's tail
  2. cons the head element onto the tail set if it's not already a member

Problem 2c: remove-elt

There's nothing to remove from an empty list, so if you get one just return it. Otherwise, check whether the head of your list is the element you're supposed to remove. If it is, also remove that element from the rest of the list, otherwise cons the head element onto the recursive subresult.

Problem 2d: set-intersect

The intersection of 'xs' and 'ys' will be a subset of xs. So simply go through all the elements of 'xs' and only include them in your result if they're also members of 'ys'.

Problem 2e: power-set

I find that power-set is easier to understand if you first define the helper function 'cons-each'. This helper takes a list of lists and conses some item onto each list. The powerset then combines all the sets which make up the powerset of the rest of the list with those same sets including the head of our input.

Problem 2f: operations on nested sets

The only thing tricky about this question was the need for mutual recursion between set-equal and set-member. It's otherwise a pretty straightforward reimplementation of functions above.