Adding higher-order type constructor to dart
SandroMaglione opened this issue · 4 comments
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?
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>
.
@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.
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".
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.