CODEWITHSUNDEEP
f#treemodeling
bright
bright

Reputation: 4811

Modeling constrained tree data structures in F#

As a beginning F# programmer, I've read articles like this one that describe how to model simple tree data structures in F#.

I'd like to model more complex tree data structures. Consider a tree that consists of a single root that has a number of child nodes (primary nodes), each of which has a number of nodes (secondary nodes).

Let's say there are three flavors of trees, which are based on the kind of root (notice I say "kind" rather than "type" - I'm not trying to assume any model yet.)

What is a good way to model this in F#? (Note: this is the start of a more complex data structure, where nodes can have attributes, and of course there will be operations that traverse trees, but I'll save that for a future question. However, as an example, all root nodes might have a Name, primary nodes an address, and secondary nodes a phone number. if you have thoughts on this as well, do mention.)

Upvotes: 2

Views: 122

Answers (1)

scrwtp
scrwtp

Reputation: 13577

This is the type I doodled:

type Node<'v, 'c> = 
    {
        Value: 'v
        Children: 'c list
    }

or as a single case discriminated union if you prefer that:

type Node<'v, 'c> = N of 'v * 'c list

Which you can later use like this to model the first tree flavor you have:

type R1 = obj
type P1 = obj
type S1 = obj

type Tree1 = Node<R1, Node<P1, S1>>

I'm assuming here that your R1, P1, S1 types are actually data that you want the nodes to carry.

This way max depth of the tree and types of the nodes are reflected in the type signature. Arguably you won't be able to have arbitrarily deep trees that way (or even deeper than few levels), since the type of the tree would quickly grow unwieldy ;) If you only care about depth-3 trees, that's not a concern.

Upvotes: 2

Related Questions