Supertypes (errors: cannot produce expected type)

Hi!
There is a type

//N-Node Tree
public type NNT<K, V> = {
    #empty;
    #parent: NNT<K, V>;
    #child: NNT<K, V>;
};

This works well if you create an empty object

public func empty<K, V>(): NNT<K, V> { #empty; };

An error occurs if I need to bind other objects. I have removed some things so as not to obscure the essence

func bind<K, V>(parent : NNT<K, V>, child : NNT<K, V>, k : Key, k_eq : (K, K) → Bool, v : V){
{ parent =parent; child = child };
};

1)How initialization takes place in supertypes? (Supertypes of a variant types are variants with additional tags, and maybe the type of some tags changed to a supertype.)
2)Will references to descendants be preserved in a complex structure?

is this really the type that you want? I appreciate that you’ve elided somethings for concision, but I would have expected something more like this, for an N-node tree:

// Version 2 (WDYT?)

public type Node<K, V> = {
  key: K;
  value: V;
  children : [Tree<K, V>];
  var parent: ?Node<K, V>;
}

In this definition (version 2), there are multiple children, stored in an array.

There is also a parent field, and in the simplest initialization procedure, that would initially be null and then set to the node’s parent after being initialized as a well-defined tree without those fields set. Do you really need it, BTW?

For question 1: Notice that I haven’t actually used any variant types. Did you want them or think that you need them for some reason?

FWIW, subtyping will work for the Node type in version two: If a value with more fields is given, it can also work as a Node. (Is that want you wanted?)

For question 2: I don’t follow entirely yet.

1 Like

Oops, meant children : [Node<K, V>];

Or equivalently, this definition too

public type Tree<K, V> = Node<K, V>

FWIW, I keep getting 403 when I try to correct the post above by editing it. Frustrating.

Hi, Matthewhammer

For question 1: Notice that I haven’t actually used any variant types. Did you want them or think that you need them for some reason?

Yes. I looked at the base class of the Trie, a binary tree, and decided to go that way.
Your version number 2 is a great option. I was dealing with the basic library and decided to do something in that style. I will do so if there are difficulties.

FWIW, I keep getting 403 when I try to correct the post above by editing it. Frustrating.

This option is working, I don’t think there will be an array as children.

public type Node<K, V> = {
    key: K;
    value: V;
    children : [Node<K, V>];
    var parent: ?Node<K, V>;
};

What about the first option, why do errors occur in the bind() function and how will it be correct?

Your original type defines a variant. A value can only be one of the cases in the type, i.e., either

#empty

or

#parent(nnt)

or

#child(nnt)

The {parent; child} you wrote on the other hand defines a record/object, so is a completely different type.

I’m not sure what the intention of the original type was, but perhaps what you wanted was a type like

type NNT<K, V> = {
  #empty;
  #node : {parent : NNT<K, V>; child : NNT<K, V>};
}

whose node values would be written as

#node{parent = nnt1; child = nnt2}

(Or alternatively, use a tuple for the argument to #node.)

1 Like