Modeling complex hierarchies in F#

Question

I'm fairly new to F#, and I want to model things in the real world that have fairly complex "has-a" relationships. At the top of the hierarchy are four types, A - D, with these relationships:

A
|
+--A
|
+--B
|  |
|  +--B
|  |
|  +--D
|     |
|     +--D
|
+--C
|  |
:  +--D
|     |
|     +--D
:

So type B can have a "parent" of either A or B, and type D can have a parent of B, C or D.

I want to use discriminated unions to constrain the parent of each type, so they can't be assigned to invalid parents, e.g:

type B_Parent = A | B
type D_Parent = B | C | D

Then I want to use records to model each type, where one field is the parent, e.g:

type A = { parent:A_Parent; ... }
type B = { parent:B_Parent; ... }
type C = { parent:C_Parent; ... }
type D = { parent:D_Parent; ... }

C_Parent isn't a problem because its parent type A is declared beforehand. And I have used 'A option' for A_Parent. But I haven't been able to work out how to define B_Parent and D_Parent, because of their nested dependency on themselves, and on other types?

Answer 1

First, one very important thing: when you write

type B_Parent = A | B

you are not declaring that B_Parent is a DU joining the two previously-defined types A and B. There is no syntax for that.

What the line above is actually doing is defining two empty subtypes of B_Parent, which have nothing to do with the original A and B. It is equivalent to:

type B_Parent = B_Parent.A | B_Parent.B

In order to re-use existing types inside a DU, you need to give a name to the case - effectively wrapping them in another type. So the proper declaration can be something like:

type B_Parent = P_a of A | P_b of B

With that aside - as Anton said, the keyword for defining mutually referential types is and. That said, it is best to keep such mutual references as small and tight as possible. So we could do something like this:

type A = { parent:A_Parent; ... }
    and A_Parent = P_a of A
                 | None

type B = { parent:B_Parent; ... }
    and B_Parent = P_a of A 
                 | P_b of B

type C = { parent:C_Parent; ... }
    and C_Parent = P_a of A

type D = { parent:D_Parent; ... }
    and D_Parent = P_b of B 
                 | P_c of C 
                 | P_d of D

We could have used just A option for A_Parent, and just A for C_Parent, but I think that keeping the case names consistent will probably make things more readable.

Answer 2

You can use the and keyword to define types that are mutually related, for example:

type B_Parent = A | B
and D_Parent = B | C | D
and A_Parent = A
and C_Parent = B
and A = { parent:A_Parent }
and B = { parent:B_Parent }
and C = { parent:C_Parent }
and D = { parent:D_Parent }

See also this related SO question. The and keyword is also helpful when defining mutually recursive functions.