Adding higher-order type constructor to dart

[SandroMaglione]

While working on a functional programming package for dart I found that dart does not support higher-order type constructors (higher-kinded type).

For example, a typical Foldable typeclass expects a generic parameter F that itself can have another generic parameter.

In scala, it is already possible to do that with the following syntax:

trait Foldable[F[_]]

As a concrete example, the type F can be a List and [_] means that the List can itself accept any type (e.g. List<int>). This feature allows defining functions like the following:

def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B

If F is List then:

B foldLeft<A, B>(List<A> fa, B b, B Function(B, A) f);

This is not possible currently in dart. The fa parameter cannot itself accept another generic parameter.

/// Not valid dart code!
abstract class Foldable<F<_>> {
  B foldLeft<A, B>(F<A> fa, B b, B Function(B, A) f);
}

/// Not valid dart code!
abstract class Foldable<F> {
  // Error: The type 'F' is declared with 0 type parameters, but 1 type arguments were given.
  B foldLeft<A, B>(F<A> fa, B b, B Function(B, A) f);
}

A workaround would be to define two generic types on the same class like in the following example:

abstract class Foldable<TypeClass, TypeData> {
  TypeClass bind<B>(covariant TypeClass Function(TypeData a) f);
}

/// Missing type parameter on IList!
class IList<Data> extends Foldable<IList, Data> {
  @override
  IList bind<B>(covariant IList Function(Data a) f) {}
}

In this example, the return type is a generic IList<dynamic>, since it is not possible to statically define a type parameter of another generic type.

Is it possible to implement this feature in the dart language?

[eernstg]

Most likely it would be possible to support higher-kinded type parameters in Dart.

I'm not sure about the implications for optimization opportunities (support for higher-kinded type parameters might prevent certain optimizations from taking place), and it might well be a lot of work to implement it, so we'd need some very good use cases. ;-)

There are some conflicts with Dart of today as well: For instance, generic types are considered to denote their "default" instantiation when no type parameters are passed. So with class C<X extends num> {}, a declaration like void f<X extends C>(X x) {...} accepts a type argument bounded by C<num>, not a higher-kinded type argument bounded by the type function that maps X <: num to C<X>.

[SandroMaglione]

@eernstg in my case I was trying to implement a functional programming package based on cats. I had some problems in modeling the Foldable class without higher-kinded type.

Based on the Language funnel, there seems to be many requests to support functional programming features in dart (Patterns, Multiple return values, Destructuring). Higher-kinded types would be another step in this direction.

[Levi-Lesches]

@SandroMaglione:

I may be a bit confused, so just to confirm, this is what I think you want to see (just without the errors, of course):

/// T can be List, Set, or any other iterable, but we don't care about the actual elements.
/// We care more about what type of iterable we're talking about than an actual iterable object
abstract class Foldable<T extends Iterable> {
  // Error: The type T is defined with 0 type parameters,
  // but 1 type arguments were given.
  B foldLeft<A, B>(T<A> iterable, B initialValue, B transform(B, A));
}

void main() {
  Foldable<List> fold1;
  // This is what I'm assuming you want to do.
  int result1 = fold1.foldLeft([true, false], 0, (int left, bool right) => left);
  // Error, since iterable has to be a List, not a Set. 
  int result2 = fold1.foldLeft({true, false}, 0, (int left, bool right) => left);
  // Not an error, but it should be, since we want to enforce a List<bool>
  int result3 = fold1.foldLeft([1, 2, 3, 4], 0, (int left, bool right) => left);
}

Assuming the above is accurate, I'll go on.

---

My first thought was "why have a T at all, if all you care about is an iterable?":

abstract class Foldable2 {
  B foldLeft<A, B>(Iterable<A> iterable, B initial, B transform(B, A));
}

It occurred to me that you may have more methods like foldRight where you want to ensure consistency between the iterables being used. Still, I would suggest just using Iterable, since it defines a common interface that should be all you need to know, and this way the user of your API has more flexibility. It seems like the most OOP-like thing to do. If you really need to insist on using the same type of iterable, maybe what you really want is to use the same object:

abstract class Foldable3<E> {
  Iterable<E> iterable;
  
  T foldLeft<T>(T initial, T transform(B, E));
  
  /// Will use the same type as [foldLeft] since they both use the same [iterable] object.
  T foldRight<T>(/* ... */);
}

---

But, if you really want to use this as a container class and really don't need the same instance but also really do need the same type of iterable, then I don't think that's possible. In general, what you're trying to do is this:

abstract class Foo<T> {
  E experiment<E>(T<E> object);
}

You can't guarantee that T can accept E as an argument -- imagine your Foldable with this crude example:

/// Works with any numeric type
class MyNumericCollection<T extends num> { }

abstract class Foldable4<T> {  // let's imagine this doesn't throw an error, like you're asking
  B foldLeft<A, B>(T<A> iterable, B initialValue, B transform(B, A));
}

void main() {
  Foldable4<MyNumericCollection> foldable = Foldable4<MyNumericCollection>();
  foldable.foldLeft<int, bool>(MyNumericCollection<int>(), 0, (int left, bool right) => left);  // A = int, B = bool
  // Error, since MyNumericCollection can't accept a bool, but Foldable4 has no way of knowing that,
  foldable.foldLeft<bool, int>(MyNumericCollection<bool>(), true, (bool left, int right) => left);  // A = bool, B = int
}

In other words, it's not safe to be able to apply generics to any type, because that type may not accept generics, or it may require a certain subtype as its generic, none of which can be known in advance. Unless you're asking for syntax to require "a class that can accept any other type as a generic".

[eernstg]

it's not safe to be able to apply generics to any type, because that type may not accept generics

We'd need to have a full kinding system added to the Dart type system in order to handle higher-order type parameters properly. The simplest non-trivial kind is type -> type, and we could use a lambda-literal-like syntax to denote them, e.g., \x.Iterable<x> is the function that maps a given type argument to Iterable of that type argument.

class C<X extends \x.Iterable<x>, Y> {
  X<Y> xs;
  C(this.xs);
  Iterable<Y> get iterableXs => xs; // OK, we'd have `X<Y> <: Iterable<Y>`.
}

void main() {
  C<\x.List<x>, int> c = C([1, 2, 3]); // OK, we'd have `\x.List<x> <: \x.Iterable<x>`.
  List<num> ints = c.xs; // OK, because `c.xs` has type `List<int>`.
}

It's a whole new dimension in the type system, and it's going to introduce a new set of cases to consider for every other part of the type system. I'm sure it would be possible, but it would also require some really good use cases. ;-)

For now, we might also want to keep in mind that these more sophisticated kinds of typing discipline can usually be replaced by a less precise typing: We will need to accept some casts here and there (where proper higher-order types might have given us full compile-time type safety), but in return we avoid a rather substantial amount of complexity.