Traversing through an arbitrary dictionary tree structure in C#

Question

I am trying to write a recursive C# function that will operate on generic dictionaries of the form IDictionary<string, T> where T is either another IDictionary<string, T> or a string.

My first failed attempt looked something like this:

public string HandleDict(IDictionary<string, string> dict){
    // handle the leaf-node here
}

public string HandleDict<T>(IDictionary<string, IDictionary<string, T>> dict){
    // loop through children
    foreach(string key in dict.Keys){
        HandleDict(dict[key]);
    }
}

I also tried variants of HandleDict<T>(IDictionary<string, T>) where T : IDictionary<string, T> but that also doesn't quite work. I know that what I want to do could be achieved through a custom class as the parameter instead of dictionaries, and that my attempts are conceptually flawed (there's no end to the recursion in the generic function). I would still like to know if there is actually a way to do what I want here using just generic IDictionaries.

Answer 1

In order to store either a Dictionary<string, string> or a Dictionary<string,??> as a value in a dictionary, you'd need to declare the dictionary to be of type Dictionary<string, object>.

public string HandleDict(IDictionary<string, object> dict)
{
    foreach (KeyValuePair<string, object> kvp in dict)
    {

Then you'd need to check for each value if it's a string or another Dictionary<string, string> or another Dictionary<string, object> -- C# performs overload resolution at compile-time, not at run-time!

        var leaf = kvp.Value as IDictionary<string, string>;
        if (leaf != null)
        {
            HandleDict(leaf);
        }
        else
        {
            HandleDict((IDictionary<string, object>)kvp.Value);
        }
    }
}

Recursion would end when a leaf is reached, because the HandleDict overload for Dictionary<string, string> does not continue the recursion.

However, as you'll note, there's a lot of type checking and casting going on, and a Dictionary<string, object> smells badly -- it essentially defeats the purpose of generics.

I suggest you have a look at the Visitor Pattern instead.

Answer 2

The C# type system is not powerful enough to represent the sort of "higher" generic types that you need to do this in the type system proper. Consider Haskell or F# if you need a language with a richer generic type system.

It is possible to do what you want in C# 4 using the 'dynamic' feature, but I'd recommend against it. Doing that basically starts up the compiler again at runtime. Rather than resorting to runtime type analysis I'd spend some time revisiting the decision to use dictionaries in the first place. I suspect there are better data structures for your actual task at hand. Describe that task and we'll see if there are better data structures.