Repository: TypeScript
Issue: Yet another Higher Kinded Types proposal in Typescript
Labels: Suggestion,Awaiting More Feedback

# Suggestion

First, let me say that this proposal is different than https://github.com/microsoft/TypeScript/issues/1213, although it achieves a similar goal. I am not proposing that type parameters be added to generic types, but rather, that classes be allowed to be instantiated like the objects that they are. I am proposing that Higher order types be added in the truest since, that is, there is a strict hierarchy of type orders, and that when one creates a class, one can assert the type of this class. 

This proposal is meant to provide a somewhat easy mechanism for both implementing and understanding the expected behavior of this highly requested feature in the near future, which takes advantage of the typescript compiler's existing infrastructure, and also Javascript's prototype inheritance. 

In addition, it covers the almost as old issue (if you include all of the tickets leading up to it) that abstract static methods be added to abstract classes and interfaces. https://github.com/microsoft/TypeScript/issues/34516 

We first note that currently, the following is valid typescript

```typescript
interface Functor<Me extends Functor<Me, unknown>, Z> {
  fmap<Y>(f : (x : Z) => Y, w : Functor<Me, Z>) : Functor<Me, Y>;
}

class MyList<X> implements Functor<MyList<X>, X> {
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  
  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}
```

We have effectively created a Functor interface, but on the wrong "level". We would like fmap to be static, but it is not. Moreover, in our Functor interface decleration, we cannot guaruntee that Z is a type paramater of Me. 

The idea is to utilize this "almost" functor interface to make a real functor interface by only slightly changing the syntax.

We allow interfaces to be instantiated with some order. So for example,

```typescript
interface^2 MyHigherOrderInterface {
     myHigherOrderMethod() : void;
}
```

This now represents a type of order 2. A normal class is automatically a type of order 1, and a value is a type of order 0.  A class is asserted to be an inhabitant of MyHigherOrderClass in a similar way to the way all values are asserted to be an inhabitant of any type, with a `:`.


```typescript
class MyLowerOrderClass : MyHigherOrderClass {
    static myHigherOrderMethod() { // Compiler error if this method isn't here and isn't static.
        console.log("Implemented");
    }
}
```

From an implementation standpoint, we are using almost (exactly in the case when there are no generics) the same code to type check that 

```typescript
class MyLowerOrderClass implements MyHigherOrderClass {
    myHigherOrderMethod() { 
        console.log("Implemented");
    }
}
```
does, but it is run on `typeof MyLowerOrderClass` instead of `MyLowerOrderClass`


Like extends, `:` can be used on generics, e.g.

```typescript
interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}
```

Unlike extensions, specializing generics in a `:` heritage clause has restrictions. They must either be specialized with generics of the inhabitant class or the inhabitant class itself, and they must all be unique. With these restrictions we have a guarantee that generics will be specialized with the type parameters of its inhabitant class. For example 

```typescript
interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}

/**
 * By our rules for inhabitants of higher order types, 
 * we have no other choice but to have the first argument be MyList<X> 
 * and the second argument be X,
 * furthermore, Z must be specialized with MyList<W> thus fmap _must_ specialize in a form we expect
 * and anything that implements functor must indeed be a functor (modulo the functor laws).
 */
class MyList<X> : Functor<MyList<X>, X> {
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  

/**
 * Here, generics of the inhabitant class are added to the generics of the method, since it is static.
 * This will be inferred from the input in this case and probably most cases, 
 * but in other cases it is a lot like having the input to the function X => MyList<X> be 'curried'
 */
  static fmap<X, Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}
```

We could try to trick it,

```typescript
/**
 * Here we are attempting to subvert the restriction that Y must be a paramater of X
 */
class MyTrick<W, X extends MyList<W>, Y> : Functor<X, Y> {...}  
```

But it won't work when we try to implement fmap, we note that the following is a compiler error in existing typescript

```typescript
class MyTrick<X, Z extends MyList<X>, Y> implements Functor<Z, Y> {

  // Compiler error on fmap
  fmap<Y>(f: (x: Y) => Y,w: Functor<Z,Y>): Functor<Z,Y> {
    throw new Error("Method not implemented.");
  }
}
```

so it would be a compiler error with `:` instead of implements as well.

We can however use a version of this trick to implement multiple versions of a functor

```typescript
/** 
 * The constraint is satisfied in current typescript, but thats okay, because map will 
 * get _statically_ specialized as a functor implementation for MyList, 
 * which is useful to have multiple functor implementations.
 */
class MyTrick<X, Z extends MyList<X>, Y> implements Functor<Z, X> {
  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
  	throw new Error("Method not implemented.");
  }
}
```
Here is a [Playground Link](https://www.typescriptlang.org/play?target=8#code/JYOwLgpgTgZghgYwgAgGIFcQLAeygHgFkUIAPSEAEwGc1Ns8iIAaZTAaxBwHcQA+VgC0+yAN4BYAFDJkMALZwADvgCafABQxkALmTrSO5IICUyALwiVrboYxZcBYkL6nddho5bI1AbikBfKSkEABs4alpCAE8AGWBqMHwADRFgOUUQiDkIcFp3ByJY+MSU1hSxKRkoCDhKHBAQqORSal0kgG0AXT9pZAR6hKh0D31aNq7TCV6ZMAALeIA6FvNm6h6ZQN7K2QVlNU1dfTbTC29mbl1ouITkl0uim7UK6eRqsHQoEGQQCBsr4vU3CW1AWu00xmM62QmwCQUkoXCkSiABUoMAEOxbsg0hksjkwHl6AV-jdSshylMZPIlKoNDBDqRjuZLOd7tcSndkCTEk9Kcg5lAeN9fsgAKJQQVQdQAImIcxwlG+ODA2PSmWy4AglAW0sh202-iAA) to these examples (which we can do because this is just existing behavior!)

Other miscellaneous things/concerns:

- Interfaces/classes can only implement/extend classes of the same order.
```typescript
interface^2 Functor<Me : Functor<Me, unknown>, Z> {
  fmap<Y, Input : Functor<Me, Z>, Result: Functor<Me, Y>>(f : (x : Z) => Y, w : Input) : Result;
}

class MyList<X> implements Functor<MyList<X>, X> { // Compiler error, A Type of order 1 can only implement or extend another type of order 1
  readonly xs: X[];
  constructor(xs : X[]) {
    this.xs = xs;
  }
  

  fmap<Y>(f: (x: X) => Y,w: MyList<X>): MyList<Y> {
    return new MyList(w.xs.map(f));
  }

}
```

- The base types of Union/Intersection/Conditional/Product types must all be of the same order.  I think there may be some fancy ways to lift this restriction in the future. For example, it may be fine to infer the order of a composite type like this to be the highest order among its leaf types, however, I am uneasy about the soundness of this.

- Ideally, `typeof X` would always have an order which is one level higher than the order of `X`. But I am not sure this would be compatible with how typescript currently works.

- My suggestion would be to first only allow higher order interfaces. But I could see something like `static super` being somewhat easily added to instantiate a higher order class, for example

```typescript
abstract class^2 MyHigherOrderClass {
     abstract myHigherOrderMethod() : void;
     
     constructor(x : string) {
         console.log(x);
     }
}

class MyLowerOrderClass : MyHigherOrderClass {
    static super("hello world") // Compiler error if this isn't called
    static myHigherOrderMethod() { 
        console.log("Implemented");
    }
}
```


Now I will list the pros and cons of this approach:

**Pros**
- Adds two highly requested features at once
- Allows us to use existing typescript to understand the expected behavior of higher order types and their relationsionship with lower order types
  rather than having to reinvent the wheel.
- Seemingly pretty easy to implement . The key thing is that parsing ^n and adding the order to a node is very easy, parsing another heritage clause is very easy. Asserting that a typeof C implements the higher order class is essentially the same asserting that a class C implements an interface with some minor tweaks (adding class level generics to the static scope), just on typeof C instead of C itself.
- Easy to reason about its soundness from a type theoretical perspective. (However, I would like feedback from someone more familiar with all of the intricacies of the language)
- Makes the problem of constraints much less challenging, since we are just implementing a "higher order" version of stuff that already exists.
- Is actually more flexible than type classes in haskell in some ways, since you can decide which paramater should be 'the' paramater 
 (in haskell, Something like Either<X, Y> could only be a functor on Y, not X, but here, you can provide both implementations), and higher orders we get for free


**Cons**
- Very Ugly. This is not as nice as the `T<~>` syntax proposed by others. However, I would argue that it is better to have something that is easy to implement to increase the likelihood of it being added to the language. 
  Having a strong foundation makes it easier to add syntactic sugar later.
- I am not sure about `typeof`, it would need to be handled carefully. Ideally, typeof would always return a type of a higher order, but I am not certain this would break existing typescript code.
- Perhaps a bit tricky for the user to understand. The fact that `Functor<Me extends Functor<Me, unknown>, X>` in the example above is essentially equivalent to something like `Functor me` in a language like haskell is not immediately obvious. But again, hopefully syntactic sugar can help with this in the future. 


## 🔍 Search Terms
Higher Order Types
Higher Kinded Types 
Abstract static methods
static methods in interfaces

## ✅ Viability Checklist

My suggestion meets these guidelines:

* [x] This wouldn't be a breaking change in existing TypeScript/JavaScript code
* [x] This wouldn't change the runtime behavior of existing JavaScript code
* [x] This could be implemented without emitting different JS based on the types of the expressions
* [x] This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, new syntax sugar for JS, etc.)
* [x] This feature would agree with the rest of [TypeScript's Design Goals](https://github.com/Microsoft/TypeScript/wiki/TypeScript-Design-Goals).


## ⭐ Suggestion

<!-- A summary of what you'd like to see added or changed -->

## 📃 Motivating Example

For me, the motivation for this was having static contracts for classes, inspired by this ticket https://github.com/microsoft/TypeScript/issues/34516#issue-507967613,
but then I realized that it could be used to implement Functors/Monads etc. See my comment https://github.com/microsoft/TypeScript/issues/34516#issuecomment-869072237 for an example of a Parseable higher order type

## 💻 Use Cases
**What do you want to use this for?**

I would love to see actual type classes and higher order types like functors and monads be in a more mainstream language. 
If pure state monads became mainstream instead of "state managers" for the front end, that would be sweet :). 

Moreover, there are many situations where static contracts are useful even for those who do not like functional style programming, for example, comparable classes when overrides are possible becomes an issue the way typescript handles assignability, because you can't gauruntee that they are all using the same comparison function without asserting that they all are exactly T (i.e. no subclasses). 

Having a static contract on a class and having methods that take the class itself based on the kind ensures that you are sorting by the same comparison method, but also allows you to have multiple comparable implementations and to mix subclasses with their superclasses. 
I.e. instead of 

```typescript

interface Comparable<X extends Comparable<X>> {
    ...
}

sort<T extends Comparable<T>>(ts : T[]);
```

You can write

```typescript
interface Comparable<X : Comparable<X>> {
    ...
}

// We can have multiple implementations of Comparable<T>, but they aren't tied to a particular subclass
// In the future it would be cool to infer the second argument if there is only one implementation like in Haskell, 
// or specify a default one.
sort<T : Comparable<T>>(ts : T[], comparisonFunction : Comparable<T>) 
```

As I mentioned above, another usecase is type parsing. Parsing with JSON.parse incorrectly introduces no errors, having a class be "parseable" in such a way that ensures an exception is thrown if it does not conform to the type would be very useful.


**What shortcomings exist with current approaches?**

The shortcomings of the existing attempts to provide a mechanism for static contracts are elucidated very clearly by Ryan Cavanaugh here https://github.com/microsoft/TypeScript/issues/34516#issue-507967613. 
The shortcomings of the existing attempts to provide a mechanism for "higher kinded types" is that they do not actually introduce true "kinds" or "orders" into the type system,  and are thus very difficult to reason about. In order for any higher kinded type system to be sound, there needs to be an explicit heirarchy. The existing approaches also involve entirely new concepts. 

This proposal only adds one new concept, which is that of orders. The other concepts are existing ones, since in Javascript you are already instantiating a new object when you create a class. 
We are just imposing the same type system as the one that already exists on these objects. This adheres to the design goal of 

> ... [using] the behavior of JavaScript and the intentions of program authors as a guide for what makes the most sense in the language.