Organizing types/namespaces within tree I'm working on a parsing engine as part of a personal project, and I'd like to expose certain .NET APIs to the parsed environment. I put together a very simple tagged union that allowed me to nest types, and put together a few functions that built up a tree of namespaces. Before going further, I decided I needed to refine the types I was using, and came up with this:

type Node =
    | Namespace of string * Node list

    | Class of string * Node list * System.Type
    | Interface of string * Node list * System.Type
    | Structure of string * Node list * System.Type
    | Enumeration of string * (string * Base.AnyInteger) list * System.Type

    | Property of string * System.Reflection.PropertyInfo
    | Field of string * System.Reflection.FieldInfo
    | Event of string * System.Reflection.EventInfo

    | Constructor of System.Reflection.ConstructorInfo
    | Function of string * System.Reflection.MethodInfo
    | Subroutine of string * System.Reflection.MethodInfo


Base.AnyInteger is another tagged union elsewhere that has cases for every .NET integer type except bigint. My expectation with these "Nodes" is that each one (except constructors) will contain their name in the string, a Node list containing any child nodes, and a reference to their System.Type or System.Reflection.___Info to provide additional information when needed. Last, I added the extra empty lines to help mentally align each level of nodes.

After defining a list of constraints that would have to be managed "in logic", I remembered that I'm not working with VB or C#, and that F#'s type system is better than what I'm used to. After about a half hour I came up with this:

type Lvl1 = Namespace of string * (Choice&lt;Lvl1, Lvl2&gt;) list

and Lvl2 =
    | Class of string * Choice&lt;Lvl2, Lvl3, Constructor&gt; list * System.Type
    | Structure of string * Choice&lt;Lvl2, Lvl3, Constructor&gt; list * System.Type
    | Interface of string * Choice&lt;Lvl2, Lvl3&gt; list * System.Type
    | Enumeration of string * (string * Base.AnyInteger) list * System.Type

and Lvl3 =
    | Property of string * System.Reflection.PropertyInfo
    | Field of string * System.Reflection.FieldInfo
    | Event of string * System.Reflection.EventInfo
    | Function of string * System.Reflection.MethodInfo
    | Subroutine of string * System.Reflection.MethodInfo

and Constructor = System.Reflection.ConstructorInfo


This new set of types correctly describes what each node can contain, using the type system to enforce everything rather than just implying how the levels are arranged with empty lines. Now nodes from Lvl1 can contain children from Lvl1 or Lvl2, nodes from Lvl2 can contain children from Lvl2 or Lvl3 (Classes and Structures may also contain Constructors), and nodes at Lvl3 cannot contain any children.

Now that I've used the type system to make sure I can't accidentally add a Namespace node inside a Class node, are there any other obvious changes I should be making here? I'll also admit I was originally using list references for each list of child nodes, because it made it easier to reason about in an imperative way; I've since revisited my code and have removed ref and started making use of map/fold/etc.
type Node


I agree with you that this is too weakly typed.



type Lvl1
and Lvl2
and Lvl3


I don't like the naming here. The name Lvl2 doesn't really say much. Better names would be something like Namespace, Type and Member (or maybe TypeMember).



Choice&lt;Lvl2, Lvl3, Constructor&gt;


I think that constructor is logically a type member, just like a property or function. So I would make Constructor another case in the Lvl3 (or Member) union. I think making the model simpler is worth having the possibility of a constructor in an interface.

With that change, struct, class and interface look exactly the same, so I would refactor it further by combining the three cases into one (called something like ComplexType), and distinguishing between them by an additional field (something like ComplexTypeKind).

Also, I would encode the possibility of a nested type by adding a case to Lvl3 (a.k.a. Member). But if you keep your current design, you should remove Lvl2 from the Interface case, because interfaces can't have nested types.



System.Reflection.PropertyInfo


There is no need to repeat the namespace name, you can open it.



Property of string * System.Reflection.PropertyInfo


Why do you keep the name, when it's already accessible through the PropertyInfo? This question applies to most of your cases.