CODEWITHSUNDEEP
genericsf#tree
UmaN
UmaN

Reputation: 915

F# Generics in Tree Structure

I have a simple type like this:

/// <summary>
/// An attribute consists of a key and all possible values.
/// </summary>
type IAttribute<'a when 'a: comparison> =
    abstract Key: string
    abstract Values: seq<'a>

From this definition I create implementations like so:

let numericAttribute values =
    { new IAttribute<float> with
        member this.Key = "Numeric"
        member this.Values = values }

let enumerationAttribute values =
    { new IAttribute<string> with
        member this.Key = "Enumeration"
        member this.Values = values }

Examples:

let numAttr = numericAttribute [| 1.0; 4.0; 6.0; 20.0; 70.0 |]
let enAttr = enumerationAttribute [| "val1"; "val2"; "val3" |]

Now I can create instances:

let num1 = new AttributeInstance<float>(numAttr, 4.0)
let num2 = new AttributeInstance<float>(numAttr, 6.0)
let en1 = new AttributeInstance<string>(enAttr, "val1")

AttributeInstance is a type that is just a tuple of a specific attribute type and a value compatible with that attribute type.

I want a simple Tree along the lines of this:

type Tree<'a when 'a: comparison> =
| Leaf of 'a
| SubTree of AttributeInstance<'a> * seq<Tree<'a>>

My problem is that at different levels of the tree I want to be able to have different types. At one level I want to have a sub tree where the attribute is en1, and at the next level I want to be able to have num1 (or num2).

Can someone help me generalize or rethink this?

Upvotes: 0

Views: 271

Answers (1)

John Palmer
John Palmer

Reputation: 25516

The problem is if you try to write something like

|Subtree of 'a * seq<Tree<'b>>

'b ends up being a new type which could create something like an infinite chain of types which the compiler doesn't support.

One way to do this can be to wrap the possible types in a Union - Something like

type Element = 
    |....

and then your tree becomes

type Tree =
| Leaf of Element
| SubTree of AttributeInstance<element> * seq<Tree>

alternatively, you can have a multi generic tree - something like

type Tree<'a,'b,'c,'d> =
| Leaf1 of 'a
| Leaf2 of 'b
...
| SubTree of AttributeInstance<'a> * seq<Tree<'a,'b,'c,'d>>

Upvotes: 3

Related Questions