Higher-kinds

[shelby3]

Kinds are the type of type constructors. Thus higher-kinds are constructors on type constructors.

Some prior discussion at the Rust forum about higher-kinds may provide a clearer understanding of what they are and use cases.

It is important to note that the supertype of a union contains more types than its subtype, e.g. Number|String is the supertype of Number. Thus we can not subsume to the greatest lower bound (aka GLB or common supertype) of the element type of an instance of an Array, e.g. from Number to Number|String, because some preexisting reference of type Array<Number> would access a data structure that contains also String elements. Thus such a subsumption will not type check. Thus we are unable to add or insert elements (into an instance of Array) which have a type that is not already the subtype of the preexisting element type. Thus employing Array with unions is not a solution to the Expression Problem, because we can't add new variants (types). Tangentially note that subsuming to the superclass for subclassing or typeclass objects (trait in Rust) works fine with Array, because the dynamic dispatch insures that no preexisting references to the Array instance are invalidated by inserting or adding elements with new subtypes to the data structure, and thus it type checks. But subclassing and typeclass objects do not (or not entirely for typeclass objects) solve the Expression Problem, because new operations can't be added (for subclassing can't be added after instantiation of the class and for typeclass objects can't be added after instantiation of the typeclass object).

But a List doesn't have this problem and is an invariant data structure, because the head of the Cons can be any type (if we are subsuming to a new union type) and any preexisting references to any element in the tail of the list will never access the new head, because a List is a singly-linked data structure with new elements prepended. Thus lists allow adding new variants (types) even for union types (not just for subclassing and typeclass objects) and since this retains the explicit union type instead of otherwise premature subsumption to a dynamic dispatch (that is employed by subclassing and typeclass objects), then we can also add new operations as a delayed binding to any future typeclass bound (having the compiler automatically generate type-case logic for the dispatch at the trait bound call site). This was my invention as a solution to the Expression Problem.

When I started thinking about how a List would interact with the first-class unions we accepted into ZenScript's design, I realized that if typeclasses can't provide a factory to construct a new instance of the data structure they are operating on, then it is impossible to write some generic operations such as a sort when employing subsuming heterogeneous unions with higher-order containers.

For example, a sort operation needs to re-order the elements of a collection which is impossible to do insitu unless all elements of the collection have the same type, which entirely defeats the goal of adding new variants (types) to the collection to solve the Expression Problem. Thus the only way to sort the List in general, is to make a new instance of a List and sort into this new List with the GLB element type. @keean suggested workarounds by passing in the factory for the value type separately. This was also mentioned by myself in another thread.

But without higher-kinds or at least Rust's Self type (which afaik is a feature that can also be obtained with higher-kinds), then I don't see how a typeclass could declare a factory method? Because the return type of the factory method needs to be the type of implementing type of typeclass, yet the Monoid needs also to know the element type, so that is a type of type constructor higher-kind pattern. This is similar to an issue we were discussing at the Rust forum about how to write the method for iterator factory in a typeclass. Note the sort operation needs to be able to return the same types as it input.

Afaik, the generalized category theory compliant interface for a factory and append operation is the Monoid typeclass. The identity method returns an empty new instance and the append adds new elements to the collection.

[shelby3]

It appears we can emit TypeScript code to implement Monoid with my hack without needing higher-kinds, but what syntax will that be in ZenScript?

data List<T> = Nil | Cons{head: T, tail: List<T>}
typeclass Monoid<T<A>> {                           // A is inferred to be a polymorphic type parameter of the implementing type because ALLCAPS
    identity(): T<A>
    append(A): T<A>
}
List<A> implements Monoid<List<A>> {
    identity() => Nil
    append(x) => Cons(x, this)
}

Since List<A> is not a subsclass of Monoid then apparently there is no higher-kinds involved, because the compiler doesn't have to reason about the constructor T<> in the context of the constructor Monoid<>. Is that correct?

P.S. 9 lines of ZenScript becomes 19 lines of TypeScript and 29 lines of JavaScript not including code to set up the prototype hack on module load, although the ECMAScript with class will be more concise.

[keean]

I don't think that is quite right. Monoid takes a parameter in no-object systems because is declaring free functions not methods:

data List<T> = Nil | Cons{head: T, tail: List<T>}
typeclass Monoid<A> { 
    identity(): A
    append(A, A): A
}
implement Monoid<List<A>> {
    identity() => Nil
    append(x) => Cons(x, this)
}

The above is how I would want to do it in a no-objects system. The following is for an object system:

data List<T> = Nil | Cons{head: T, tail: List<T>}
typeclass Monoid {
    identity(): This
    append(This): This
}
List<A> implements Monoid {
    identity() => Nil
    append(x) => Cons(x, this)
}

[keean]

There is a further small problem with the above, identity is effectively a constructor function, so the second example is not quite right. Infact we would have to introduce a new keyword to make identity a static function in C++ terminology. The first example (non-objects) is correct though.

[shelby3]

@keean wrote:

data List<T> = Nil | Cons{head: T, tail: List<T>}
typeclass Monoid<A> { 
    identity(): A
    append(A, A): A
}
implement Monoid<List<A>> {
    identity() => Nil
    append(x) => Cons(x, this)
}

The above is how I would want to do it in a no-objects system.

Your append doesn't make any sense. The x has to have the type of the elements of List<A>. What does append(A, A): A mean when you implement it with append(x) => Cons(x, this)?

[keean]

You are right, my implementation is wrong, but the type signature is correct, I was too quick cut-and-pasting from the posted code:

append(x, y) => match(x):
    Nil -> return y
    Cons(h, t) -> Cons(h, append(t, y))

[shelby3]

@keean wrote:

append(x, y) => match(x):
    Nil -> return y
    Cons(h, t) -> Cons(h, append(t, y))

Yours is apparently the category theory correct Monoid and mine wasn't, but I don't see how you can implement the sort generically for invariant List with the above? Will we have another typeclass interface that can return any range (by iterators) of itself cloned (can't be just a reference to an existing Cons because that will violate the invariance requirement of my use-case and also because must clone to take range of a Cons unless the list is aware of the concept of range with an end point other than Nil)? Or do we just use a clone typeclass to get a copy (so that there are no other references into our copy so we don't have to worry about violated invariance) and sort in place on that? But sort in place (generically) on a list is very inefficientimpossible/meaningless (must prepend each element in order).

Edit: seems the most efficient way to sort a list is to convert it to an array, sort, then convert it back to list. So how to do that generically?

Seems the only way is to have typeclass interface which converts to and from an array.

Perhaps it is instructive that category theory doesn't help us, except maybe to warn of us to not try to do it with the incorrect Monoid example I showed.

[shelby3]

@keean wrote:

Infact we would have to introduce a new keyword to make identity a static function in C++ terminology.

I showed how to do it in TypeScript using only type parameters. Perhaps you mean without the unsound runtime exceptions I had to use?

[keean]

To efficiently sort a list, try a merge-sort. Recursively split the list into two (can be done with references to the source list without changing it). When you get to single items take each item and put into a separate list. Then perform a merge operation on each pair of lists, repeatedly until only one list remains which will be sorted.

The merge operation uses three lists, two input and one output. whilst there is an element in both source lists, it takes the lowest head of the two (or highest depending on desired order) and pushes it into the output list removing it from the input list. This repeats until one or both input lists are empty. If both are empty the merge is finished, otherwise we push the remaining items into the output removing them from the input, as they will already be in order.

[shelby3]

Trade-off of prematurely specializing the algorithm?

[shelby3]

Cross-referencing …

@shelby3 wrote:

…

Higher-kinded Types

Isomorphic to distilling the higher-ranked issues, higher-kinded types (aka HKT) are higher-order type constructors where the ‘kind’ means the “type” (aka meta-type) of a type constructor with meta-type variables, e.g. kind of order 0 * for primitive types such as Int, kind of order 1 * → * for List[T] and * → * → * for Either[A, B], and kind of order 2 (* → *) → * for Functor[List[T]] and (* → * → *) → * for Functor[Either[A, B]]. Higher-kinded types are required to generically (type safely) abstract over generics such as for Functor.map (also) and iteration. TypeScript does not support HKT.

[shelby3]

We must support HKT.