7 5/31: Changing associations

The goal of this lab is to practice designing visitors, equality methods, and mutable structures.

Association lists

We saw association lists on today’s exam, which are used to associated keys with values. We can represent associations as follows:

interface Assoc<K,V> {}

class EmptyAssoc<K,V> implements Assoc<K,V> {}

class ConsAssoc<K,V> implements Assoc<K,V> {

K key;

V val;

Assoc<K,V> rest;

ConsAssoc(K key, V val, Assoc<K,V> rest) {

this.key = key;

this.val = val;

this.rest = rest;

}

}

You wrote a same method that determined whether two association lists were the structurally equal. But structural equality doesn’t really embody what it means for two association lists to be the same association. For example, the following two associations represent the same information:

Assoc<String,Integer> a1 =

new ConsAssoc<String,Integer>("Fred", 40,

new ConsAssoc<String,Integer>("Wilma", 95,

new EmptyAssoc<String,Integer>()));

Assoc<String,Integer> a2 =

new ConsAssoc<String,Integer>("Wilma", 95,

new ConsAssoc<String,Integer>("Fred", 40,

new EmptyAssoc<String,Integer>()));

Moreover, since we really only pay attention to the first association of any key in a list, a1 and a2 also represent the same information as this list:

Assoc<String,Integer> a3 =

new ConsAssoc<String,Integer>("Wilma", 95,

new ConsAssoc<String,Integer>("Fred", 40,

new ConsAssoc<String,Integer>("Wilma", 42,

new EmptyAssoc<String,Integer>())));

If two association lists are structurally equal, that certainly implies they represent the same information, but as these examples show, two association lists that are structurally distinct can still represent the same association.

Exercise 1. Design a same method that determines if this association list and a given association list represent the same information. (You may need to design one or more helper methods to solve this problem.)

You can use this notion of equality to override equals as follows:

public boolean equals(Object that) {

return (that instanceof Assoc)

&& this.same((Assoc<K,V>)that);

}

Notice that you must have that be of type Object in order to override the built-in equals method (contrary to what was said in class). You may get warnings about the cast, but they can be ignored for now (Java is fundamentally broken when it comes to casting and parameterized types.)

Exercise 2. Design a hashCode method that is compatible with the above notion of equality. Your method must be able to distinguish at least three different association lists (thus always return a constant will not suffice.)

Mutable association lists

Let’s now revise the design of association lists to make them mutable, meaning we can change values associated with a key and we can add new key-value pairs.

Here is the interface that mutable association lists should support:

// Represents a mutable association of keys and values.

interface MAssoc<K,V> {

// EFFECT: Add given key, value pair to this assoc.

void add(K key, V val);

// EFFECT: Update value associated with given key in this assoc.

// Produces the old value associate with the key.

// (Throws an exception if key is not in this assoc.)

V update(K key, V val);

// Get the value associated with given key in this assoc.

// (Throws an exception if key is not in this assoc.)

V get(K key);

}

Note that it does not make sense to compare mutable hash tables for structural equality or interpreted equality. That’s because when we represent something with a mutable structure, we are representing information about sharing. So for a mutable structure, the only sensible notion of equals is the default one, which is intensional equality.

Exercise 3. Design an implementation of the above interface.

Here’s a hint about the representation of an MAssoc: you won’t be able to follow the same structure as for Assoc. Why? The answer has to do with add. Think about it and try to articulate why this design won’t work.

A design that will work is to have a mutable association contain an Assoc as data. You may have to add an update to your Assoc interface, however.

Regardless of your design, it should always be possible to view the data in a mutable association list as though it were just a plain old association list. Thus, it should be possible to use any computation formulated as an AssocVisitor as a computation over a mutable association list, too.

Exercise 4. Add a <R> R accept(AssocVisitor<K,V,R> v); method to the MAssoc<K,V> interface so that you can re-use any association list computation on mutable association lists.