...Removing All Doubt

CLR's standard Dictionary<K,T> allows you to express the type of the key and the type value so you don't have to cast on the way in and out of a dictionary. For example you can cache a bunch of strings based on some integer key. I use this in the following program that takes an integer number and writes out the English equivalent.

    class Program {
        static Dictionary<int, string> names = new Dictionary<int, string>();

        static Program() {
            names[0] = "zero";
            names[1] = "one";
            names[2] = "two";
            names[3] = "three";
            names[4] = "four";
            names[5] = "five";
            names[6] = "six";
            names[7] = "seven";
            names[8] = "eight";
            names[9] = "nine";
            names[10] = "ten";
            names[11] = "eleven";
            names[12] = "twelve";
            names[13] = "thirteen";
            names[14] = "fourteen";
            names[15] = "fifteen";
            names[16] = "sixteen";
            names[17] = "seventeen";
            names[18] = "eighteen";
            names[19] = "nineteen";
            names[20] = "twenty";
            names[30] = "thirty";
            names[40] = "forty";
            names[50] = "fifty";
            names[60] = "sixty";
            names[70] = "seventy";
            names[80] = "eighty";
            names[90] = "ninety";
            names[100] = "hundred";
            names[1000] = "thousand";
            names[1000000] = "million";
            names[1000000000] = "billion";
        }

        static int WriteValue(int value, int place) {
            if (value >= place) {
                int subValue = value / place;
                WriteValue(subValue);
                Console.Write(" {0} ", names[place]);
                value = value % place;
            }
            return value;
        }

        static void WriteValue(int value) {
            int originalValue = value;
            if (value < 0) {
                value = -value;
                Console.WriteLine("negative ");
            }
            value = WriteValue(value, 1000000000);
            value = WriteValue(value, 1000000);
            value = WriteValue(value, 1000);
            value = WriteValue(value, 100);
            if (value > 20) {
                int subValue = (value / 10) * 10;
                Console.Write(names[subValue]);
                value = value % 10;
                if (value == 0)
                    return;
                Console.Write("-");
            }
            if (value != 0 || originalValue == 0)
                Console.Write(names[value]);
        }

        static void Main(string[] args) {
            while (true) {
                Console.Write("Enter number: ");
                string line = Console.ReadLine();
                if (line == "exit" || string.IsNullOrEmpty(line))
                    break;
                int value;
                if (int.TryParse(line, out value)) {
                    WriteValue(value);
                    Console.WriteLine();
                }
                else
                    Console.WriteLine("Error: expected number");
            }
        }
    }

This example doesn't use any casts. The expression names[10] is of type string and the index is of type int. This is great when the values of the dictionary are all homogeneous as name is above. But what if I want to store values of varying types but still not use a cast. In other words, I want a heterogeneous, type-checked dictionary. If I don't mind casts, I can just use a Hashtable as in,

    Hashtable table = new Hashtable();

    table.Add("k1", "one");
    table.Add("k2", 2);
    table.Add(3, 3.33);

    string v1 = (string)table["k1"];
    int v2 = (int)table["k2"];
    double v3 = (double)table[3];

    Console.WriteLine("v1 = {0}", v1);
    Console.WriteLine("v2 = {0}", v2);
    Console.WriteLine("v3 = {0}", v3);

Unfortunately, if I later change the code to,

    table.Add("k1", 1);
    table.Add("k2", 2);
    table.Add(3, 3.33);

    string v1 = (string)table["k1"];
    int v2 = (int)table["k2"];
    double v3 = (double)table[3];

The compiler will dutifully compile the code and I will get a runtime error at the first use of the dictionary when it tries to cast an integer to a string. I would like the compiler to catch this type of error instead of having to wait until my user does.

I have keys of varying type and values of varying type. How can I get this and type verification as well? In other words, what I want is something like,

    dictionary.Add(k1, "one");
    dictionary.Add(k2, 2);
    dictionary.Add(k3, 3.33);

    string v1 = dictionary[k1];
    int v2 = dictionary[k2];
    double v3 = dictionary[k3];

What I want to do is be able to infer the returns result of the expression dictionary[k1] from the key. In the above example, there should be something about the k1 key that tells the compiler that the result will be a string and when I change it later to an int, I want the compiler to catch the assignment to string as a type error.

To do this I need a method that can infer the type of the return result from a parameter. A simple example of such a method is,

    T NoOp(T value) { return value; }

which returns the same value of the same type as it retrieves for any value of any type. The return type is inferred from the parameter value's type.

This is not good enough yet. We don't want the key type to be the same as the value type; we want the value type to be arbitrary. To do this we need to encode the value's type in the key. One way is to have the key's type include the value's type as part of the key's type definition. This can be done through supplying a dummy type parameter, a type parameter that is not needed in the definition of the type but the dummy type parameter is carried around by the type and can be used by type inferencing. To do this we need a method something like,

    T Get<T>(Key<T> key) { ... }

which takes a key and extracts the return type from the keys definition. This requires a Key class definition that has one type parameter which is simply,

    class Key<T> { public Key() { } }

Note we don't use T in Key, it is just there so type inferencing will find it. We can now define some keys,

    Key<string> k1 = new Key<string>();
    Key<int> k2 = new Key<int>();
    Key<double> k3 = new Key<double>();

The keys are just arbitrary instances. Type inferencing will now be able to extract T from the key's type and use it as the return result! This means that Get(k1) will be  of type string and Get(k2) will be of type int.

Type inferencing also works the same way for other parameters of the method. For the Add() method we can define it as,

    public void Add<T>(Key<T> key, T value);

With this  Add() the code above will compile because the type of value is also inferred from the key!

Unfortunately, the this property does not accept type parameters so we cannot get the code,

    string v1 = dictionary[k1];
    int v2 = dictionary[k2];
    double v3 = dictionary[k3];

to compile; but if we replace the array indexers with a Get() method we can get close, as in,

    string v1 = dictionary.Get(k1);
    int v2 = dictionary.Get(k2);
    double v3 = dictionary.Get(k3);

This works if dictionary has a Get() method like we described above,

    public T Get<T>(Key<T> key);

There we have it! With the Add() and Get() methods we have the beginnings of a dictionary that can hold any value of any type and retrieve the value back without requiring our use of the dictionary to use a cast. A complete example is given below,

    class Key<T> { public Key() { } }

    class PolyDictionary {
        private Dictionary<object, object> _table;

        public PolyDictionary() {
            _table = new Dictionary<object, object>();
        }

        public void Add<T>(Key<T> key, T value) {
            _table.Add(key, value);
        }

        public bool Contains<T>(Key<T> key) {
            return _table.ContainsKey(key);
        }

        public void Remove<T>(Key<T> key) {
            _table.Remove(key);
        }

        public bool TryGetValue<T>(Key<T> key, out T value) {
            object objValue;
            if (_table.TryGetValue(key, out objValue)) {
                value = (T)objValue;
                return true;
            }
            value = default(T);
            return false;
        }

        public T Get<T>(Key<T> key) {
            T value;
            if (!TryGetValue(key, out value))
                throw new KeyNotFoundException();
            return value;
        }

        public void Set<T>(Key<T> key, T value) {
            _table[key] = value;
        }
    }