FAQ for Homework 3: Sets

What should I read for help on this homework assignment?

Problem 3

How can I find the maximum of two values?

You can use max a b to find the maximum of a and b.

How do we define `size`?

Size is defined as the number of nodes in a tree, so for an empty tree, the size would be 0, and for a single node tree, it would be 1.

How do we define `height` for a tree with a single node?

In CIS 1200, we define height by levels of nodes. So a single node has height 1. The empty tree has height 0.

Runtime error – The implementation `tree.ml` does not match the interface `tree.cmi`: Values do not match

Your implementation is forcing OCaml to treat the generic 'a as an int, when you should be allowing the generic 'a to be generic.

For example, if I write:

let my_function (x: 'a) = 1 + x

I am forcing x to be an int even though it is declared as a generic 'a, because I combine it with 1 using the int operator +.

Problem 5

How should I test `OLSet` and `BSTSet`?

When testing inside the module, you can write tests by simply calling functions as you would at the top level, because the underlying data structure is visible to you, as you’re inside the module.

In the SetTest module, you will only have access to the functions defined in setInterface.ml (so you can’t directly test the data structure of the implementation). When it’s run against either OLSet or BSTSet, SetTest will call the implementation specified within the modules but does not have visibility to the underlying data structure.

One of my tests won’t pass either as a regular or a failing test. How is this possible?

A regular test expects a boolean, and passes if the boolean is true, while a failing test only passes if the output of the involved function is a failwith.

Therefore, if you’re trying to test the “opposite” of the test case to see if that makes the test pass, instead of using run_failing_test you should use the keyword not to negate the value of the boolean expression.

Problem 6

What is an invariant?

An invariant is a conceptual rule/assertion about the program state (not something explicitly written as code). A function that ensures that the invariant holds is said to maintain the invariant.

For data structures, they are guarantees that the data structure will act in the way we expect them to. Some examples:

BSTs - Empty is a BST, and for any BST Node (lt, x, rt)
lt and rt are BSTs
all values in lt < x
all values in rt > x
Sets - Elements are unordered and cannot repeat
Lists - Elements are ordered and can repeat
Ordered Lists - Elements that come earlier are less than or equal to later ones.

What’s the purpose of `OLSet`? If a set is just a list, why can’t we use the functions for lists we implemented in `higherOrder.ml`?

A list is one way of representing a set. The point of this problem is to illustrate the difference between the abstract type set and one concrete representation of sets, namely, lists. In fact, there are multiple ways of representing sets as lists, each of which corresponds to different invariants that will be established/maintained by the set operations.

In OLSet, you must represent sets as sorted lists with no repeated elements. With this invariant, there is exactly one suitable representation of any set. For instance, for the set {1, 2}, it is the sorted list [1;2]. With this invariant, the list [2;1] is not a valid representation of the set. The payoff is that, while ‘add’ will be more complex, the operations of ’elements’ and ’equal’ will be very easy.

Can we assume that the input `'a` set is sorted and follows the invariants?

Yes. Any value of type 'a set must follow the invariants.

General

Can I re-use functions I wrote in other modules?

Yes. You might have to prefix them with module name like HigherOrder.fold if that module isn’t explicitly opened with ;;.

Can I add rec to a function where it isn’t used?

You may not add the rec keyword to a function header we have provided for you. However, you are welcome to make recursive helper functions. Generally, if the function header does not contain rec already, this might be a hint that there’s a simpler, non-recursive way to write the function!

Can I compare values of any type with `<`, `>`, and `=`?

The comparison operators (<, >, <=, >=, =) all have type 'a -> 'a -> bool. So they are available in generic functions. For this to work, however, OCaml needs to define what they should do for specific types (int, string, bool, list, other datatypes). For strings, the comparison is “lexicographic,” i.e. it puts strings in the order that they appear in the dictionary. You might play around a bit to see what happens with other types. (The OCaml docs have more info here).

Can we use functions in the OCaml-provided `List` module?

You cannot use any function from the List module in this homework unless specified. This rule includes the function List.sort.

However, you can use append (the @ operator) and max.