Currently, I am developing a TypeScript implementation of a recursive binary search tree (BST) data structure using generic constraints. In order to establish a default for the recursive generic variable T without directly using it in the default declaration (as that is not allowed), I have employed co-recursive logic as a 'base case' for the constraint. The code snippet below illustrates this approach:
// Utilizing bounded polymorphism with recursive generic constraints.
type IBSTBoRecDflt<K, V> = IBSTBoRec<K, V, IBSTBoRecDflt<K, V>>;
interface IBSTBoRec<K, V, T extends IBSTBoRec<K, V, T> = IBSTBoRecDflt<K, V>> {
key: K;
value: V;
left?: T;
right?: T;
}
type BSTBoRecDeflt<K, V> = BSTBoRec<K, V, BSTBoRecDeflt<K, V>>;
class BSTBoRec<K, V, T extends BSTBoRec<K, V, T> = BSTBoRecDeflt<K, V>> implements IBSTBoRec<K, V, T> {
key: K;
value: V;
left?: T;
right?: T;
constructor(key: K, value: V, left?: T, right?: T) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
const t = new BSTBoRec(5, 'e', undefined, new BSTBoRec(8, 'h'));
An issue arises where the type inference seems to be incorrect for the right branch (8, h) when a left branch is missing. Upon executing new BSTBoRec(8, 'h'), we encounter the following error on the last line:
Argument of type 'BSTBoRec<number, string, BSTBoRec<number, string, undefined>>' is not assignable to parameter of type
'BSTBoRec<number, string, BSTBoRec<number, string, BSTBoRec<number, string, undefined>>>'.
Type 'BSTBoRec<number, string, undefined>' is not assignable to type
'BSTBoRec<number, string, BSTBoRec<number, string, undefined>>'.
Type 'undefined' is not assignable to type 'BSTBoRec<number, string, undefined>'.
The error can be resolved by explicitly specifying the types K and V for the (8, h) branch:
const t = new BSTBoRec(5, 'e', undefined, new BSTBoRec<number, string>(8, 'h'));
In conclusion, there seems to be an issue with the type inference specifically when the left branch is omitted. Any insights into this behavior would be greatly appreciated.
For reference, you can view a live example of the code and error on this playground link.