Function composition type inference in Dart

Question

In dart, with generics,

the identity function works as below:

a to a:

var id = <A>(A a) => a;

a to the list type [a]:

var list = <A>(A a) => [a];

Now, I have function composition compose:

var compose = 
   <A, B>(B Function(A a) f) =>
      <C>(C Function(B b) g) => 
                       (A a) => g(f(a));

C Function(A) Function(C Function(B)) Function<A, B>(B Function(A)) compose

then compose id and list

var idList = compose(id)(list);

I want the type of idList should be :

List<A> Function<A>(A)

but the actual type inference is:

dynamic Function(dynamic)

Is it possible to improve the situation?

lrn · Accepted Answer · 2022-07-02 09:43:11Z

3

The result of the two invocations is (A a) => g(f(a)).

That is not a generic function, so it won't have type X Function<A>(Y) for any X or Y.

It's not possible to "abstract over genericity", and Dart does not have first class generic types, so it's going to be incredibly difficult to create a general compose that works on generic functions.

If you try just returning a generic function, it won't work.

var compose =   // BAD, WON'T WORK
   <A, B>(B Function(A a) f) =>
      <C>(C Function(B b) g) => 
                    <A>(A a) => g(f(a));

The type of f and g are locked further out, when the A, B and C types arguments were provided.

If you try to require the argument functions to be generic:

var compose =   // BAD, WON'T WORK
    <B>(B Function<X>(X) f) =>
    <C>(C Function<X>(X) g) => 
                     <A>(A a) => g(f(a));

it still won't work because B and C are still provided outside of the scope of the <X> scopes, so they can't depend on X, which they should in your case.

The real issue is that the function types A Function<A>(A) and List<A> Function<A>(A) are pretty much unrelated to every other function type, as subtyping on functions is defined.

You can only treat a type generically, if there is a supertype you can treat it as. That's why foo<T extends num>(T x) => x.toRadixString(2); is not valid, you must treat x as num everywhere, because that's the only thing you know about it for sure.

So, for the compose to work, it needs to be written as:

var compose =   // TOO SPECIFIC
          (A Function<A>(A a) f) =>
    (List<B> Function<B>(B b) g) => 
                        <A>(A a) => g<A>(f<A>(a));

because that's the only general types that your actual function arguments are subtypes of and which allows you to get the result structure you want by looking only at the generic bounds.

In short, no, it's not possible to improve the situation.

Dart cannot abstract over a generic type, so you can't do A<Y> foo<A<X>, Y>(A<X> f<X>(X x), Y y) => f<Y>(y); and have it abstract over the return types of the generic functions in a way that includes the function's type argument. That's the thing that could potentially make it work. You'd still need separate compose functions for generic and non-generic functions (and one for each structure of generic type-parameter vector).

answered Jul 2, 2022 at 9:43

lrn

72.8k7 gold badges122 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

SmoothTraderKen Over a year ago

Thanks always. >"The result of the two invocations is (A a) => g(f(a)).That is not a generic function" Well, in function composition, the output function's A is determined by the first generic A See fsharpforfunandprofit.com/posts/function-composition, please.

SmoothTraderKen Over a year ago

I think I did nothing wrong with my genric code, and unfortunately, the type system in Dart is pretty much limited as you have shown. Thanks again.

lrn Over a year ago

Dar is indeed limited compared to F#. The F# compose has type ('a -> 'b) -> ('b -> 'c) -> ('a -> 'c). It's not clear where the "∀c" quantifier goes, and that is part of F#'s treatment of generics. In F#, every function can be generic, generic functions are not special kinds of functions. An 'a -> 'a is-a int -> int (I think). In Dart, an A Function<A>(A) is-not-a int Function(int). You can assign the former to the latter, but that does an implicit specialization, so int Function(int) f = id; is really int Function(int) f = id<int>. Fundamentally different type systems.

Collectives™ on Stack Overflow

Function composition type inference in Dart

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related