Function composition challenge for type system

[Igorbek]

How would you type the following JavaScript function?

function wrap(fn) { return (a, b) => fn(a, b); }

Obviously, the naive typed declaration would be:

type Func<A, B, R> = (a: A, b: B) => R;
declare function wrap<A, B, R>(fn: Func<A, B, R>): Func<A, B, R>;

But it does not really describe its contract. So, let's say if I pass generic function, which is absolutely acceptable, it's not gonna work:

const f1 = wrap(<T>(a: T, b: T): T => a || b);

It's clear that f1 must be <T>(a: T, b: T) => T, but it's inferred to be (a: {}, b: {}) => {}. And that's not about type inferring, because we wouldn't be able to express that contract at all. The challenge here is that I want to be able to capture/propagate not only the generic parameters themselves, but also their relations. To illustrate, if I add an overload to capture that kind of signatures:

declare function wrap<A, B, R>(fn: <T>(a: T, b: T) => T): <T>(a: T, b: T) => T;

then, I still wouldn't be able to express

const f2 = wrap(<T>(a: T, b: T): [T, T] => [a, b]);

Because then I would need to add overloads of unbounded number of type compositions, such as [T], T | number, [[T & string, number], T] | Whatever ... infinite number of variations.

Hypothetically, I could express with something like this:

declare function wrap<F extends Function>(fn: F): F;

but it doesn't solve the problem either:

• F isn't constrained to be requiring at least 2 arguments
  • F extends (a: {}, b: {}) => {} would work, but doesn't currently, because it collapses F to (a: {}, b: {}) => {}
• it doesn't allow to express modified signature components of F; see an example below

So then we come to more complicated things:

const wrap2 = fn => args => [fn(args[0], args[1])];
// so that
const f3 = wrap2((a: number, b: string): number|string => a || b); // (args: [number, string]) => [number|string]

How to express that in the type system?

A reader can think now that is very synthetic examples that unlikely be found in real world. Actually, it came to me when I tried to properly type Redux store enhancers. Redux's store enhancers are powerful and built based on function compositions. Enhancers can be very generic or can be applicable to specific types of dispatchers, states etc etc. And more importantly they can be constructed being detached from specific store. If the issue falls to discussion I will provide more details of why it's required there.

So where's the proposal? I've been thinking of that for awhile and haven't came out with something viable yet. However, this is something we can start with:

declare function wrap2<~G, Ʀ<T1, T2, R, ~G>>(fn: <...G>(a: T1, b: T2) => R): <...G>(args: [T1, T2]) => [R]);

Of course, ignoring the syntax, here's what was introduced:

1. ~G is generic set of unbinded (no such word?) generic parameters with their constraints. Since it's not the same as generic type parameter, I've marked it with ~. So than it's applied as <...G> that means that set becomes set of generic parameters. For example ~G=<T, R extends T>, so then <...G>=<T, R extends T>.
2. Ʀ<T1, T2, R, ~G> (maybe syntax Ʀ<T1, T2, R, ...G> would make more sense, btw) is a relation between T1, T2, R, ~G. It is another kind of generic information. It could be a set of relations, such as T1=number, T2=string, R=T1|T2=number|string. Important here, is that relations can introduce new names that can be used as generic parameters, and also, they can reference existing type parameters from enclosing generic info.

Probably, examples could help to understand what I'm trying to say:

// JavaScript
const f(f1, f2) => a => b => f2(f1(a), b);
// TypeScript
declare function f<~G1, ~G2, Ʀ<~G1, ~G2, A, B, R1, R2>>(
  f1: <...G1>(a: A) => R1,
  f2: <...G2>(r1: R1, b: B) => R2): <...G1>(a: A) => <...G2>(b: B) => R2;

// using
const g = f(
  /* f1 = */ <T>(a: [T, T]): [T, T] => [a[1], a[0]],
  /* f2 = */ <T, B extends T>(r1: [T, T], b: B[]): B[] => [...r1, ...b]);
// Inferred generic data (all can be set explicitly, syntax is pending):
// ~G1 = <T>
// ~G2 = <T, B extends T>
// Ʀ<~G1, ~G2, A, B, R1, R2> ->
//   A is [G1.T, G1.T],
//   R1 is [G1.T, G1.T],
//   R1 is [G2.T, G2.T],
//   B is G2.B[],
//   R2 is G2.B[]
// So the return type, type of const g would be
// <...G1>(a: A) => <...G2>(b: B) => R2 ->
//   <T>(a: [T, T]) => <G2_T extends T, B extends G2_T>(b: B) => B[]

Simpler example from the beginning:

// JavaScript
function wrap(fn) { return (a, b) => fn(a, b); }
// TypeScript
declare function wrap<~G, R<~G, A, B, C>>(
  fn: <...G>(a: A, b: B) => C): <...G>(a: A, b: B) => C;

// using
const f1 = wrap(<T>(a: T, b: T): T => a || b);
// is the same as explicitly
const f1: <T>(a: T, b: T) => T =
  wrap<
    /* ~G = */ ~<T>,
    <~<T>, A, B, C> -> [
       A is T,
       B is T,
       C is T]
   >(<T>(a: T, b: T): T => a || b);

Ok, guys, what do you think of this?

[yahiko00]

This seems really interesting and shows that some typings are not that easy, especially when it comes to pure functional programming. I think the language should go on moving to enhance its typing system (its name is TypeScript), but personnally, I feel embarrassed when I see perfectly correct typings, but rather hard and annoying to understand. I sometimes have troubles to simply locate parameters in the signature when there are a lot of generics and advanced typing features. Maybe this readability issue should be taken someway into account.

[Igorbek]

@yahiko00 thank you for the feedback. It's a good point about readability, however I didn't tried to find great syntax by now and we'd do it later if it lands. This proposal is purely for discussion and attempt to express really complicated functional concepts. I try to address the complexity of type flow when it comes to generalization. We can capture types in generic fashion but cannot catch generics themselves.

[unional]

One idea (relate to #10215) is to have the ability to describe the functional contract into two pieces:

// Pseudo code !!!
function wrap<T extends Function<Args, Ret>>(fn: T): PromiseLike<Ret>;

That may allow us to declare types that override either Args or Ret.

[Igorbek]

@unional yes, that might work if Args would be a variadic generics #5453 in form of ...Args, however it wouldn't generalize variations where captured function has generics. So if I pass <T>(x: T) => T it's not gonna work, just because Function<Args, Ret> has no generic parameters defined. Moreover, it doesn't reflect relations between them (like in <A,B>(a: A, b: B) => A|B, where return type is composition of generic type arguments).

[unional]

Yes, which is essentially what's your OP is about, right? 👍

[unional]

However, should the function aware the generic parameters to begin with? If the argument is a function, user can always have a reason to pass in a function with generics.

So it think this problem should not be tackled by "adding generic constructs" to capture it, but "allowing argument to capture generic from 'function with generics'".

Just thinking out loud.

EDIT: Of course, this may be the end goal and what you are describing is how to declare that explicitly. 🌷

[Igorbek]

I'm pretty sure, it should. So let's say we take your example:

// Pseudo code !!!
//function wrap<T extends Function<Args, Ret>>(fn: T): PromiseLike<Ret>;
// I modified it to what I think you tried to express, using variadic kinds
function wrap<T extends Function<...Args, Ret>>(fn: T): (...Args) => PromiseLike<Ret>;

And pass that function

function identity<T>(x: T): T { return x; }
const wrappedIdentity = wrap(identity); // what would the type of wrappedIdentity?
// and even if we pass generic arguments explicitly
wrap<T, T>(identity); // what is the T here?

My point is that currently we only have first level of generalization, where function can abstract from concrete types it operates with. And this level cannot generalize itself, because it operates with concrete type. I am proposing second level, where the first level's generalization can be generalized :) You may ask, would we need third level? I'm pretty sure we wouldn't, because capturing all the generic abstraction into a generic parameter would be able to capture on the same level.

[KiaraGrouwstra]

A reader can think now that is very synthetic examples that unlikely be found in real world.

Composition and currying are the cornerstones of functional programming, and both quickly break down when used with generics -- see my linked thread listing several related issues filed at typescript-ramda. This is only as exotic as FP in JS: that is to say, rapidly gaining traction.

This proposal [...] attempts to express really complicated functional concepts.

It can be expressed pretty succinctly. My minimum reproduction might help there: compose(identity) already breaks down.

I feel embarrassed when I see perfectly correct typings, but rather hard and annoying to understand.

I feel you there, but I imagine most users won't have to run into this. I don't mind leaving the hard stuff here with definition writers of FP libs, so that users can just use the functions. I think for some functions the type definitions can definitely be harder to understand than just explanations. And I think that's fair, because those are aimed at filling distinct purposes: explanations are for humans, while type definitions in the first place need to enable proper inference about return types, which admittedly can be tough. Take, say, my path typings. The docs explain better, but hey, it calculates the result type for you so you don't have to annotate it manually.

For capturing generics, I like the idea of using a spread as in the variadic kinds proposal you mentioned, but in his compose and curry examples he unfortunately skipped over generics of supplied input functions. I'm trying to think of how this could address e.g. the compose definition.

So we'd have, e.g. for 1 function, 1 parameter (skipping variadics to generalize those to keep it simple), compose<V0, T1>(f0: (v0: V0) => T1): (v0: V0) => T1;. So we could try to capture generics there and try to embed them in the main function such that the generics would not go lost: compose<V0, ...G0, T1>(f0<...G0>: (v0: V0) => T1): <...G0>(v0: V0) => T1;.

Points I'm thinking about:

• Decomposing ...G0 into a result function might cause name clashes when there are multiple spreads like that. In that event maybe it'd need to start name-spacing resulting generics' names.
• Is it useful to add ...G0 back into the result function like that in the first place? We're not directly accessing the contained generics there, so aren't V0 and T1 still defined in terms of the original generics rather than using this "new copy"? Or are generics passed "by reference"?
  • If passed 'by reference', good. Otherwise, this would become sort of useless, and we'd need to look for an alternative. Perhaps compose<V0, ...G0, T1>(f0<...G0>: (v0: V0) => T1): (v0: V0) => T1;, that is, not manually re-injecting the generics. This would raise other questions:
  • Should "saving" the generics in the outer function suffice here to make sure they don't go lost?
    • That's the idea in this case.
  • How would TS name generics captured this way, in case they'd stay relevant for the resulting function?
    • If this compose function captures identity there, the resulting function might retain one generic named e.g. G0.T.
  • Follow-up question: how might it infer which generics stay relevant in the resulting function, considering they're not mentioned there?
    • So V0 and T1 are types defined in f0. I think the fact these depend on G0.T should indicate that this generic retains relevance. Might need further opinions here.
• What's the addition we're shooting for here, if there is significant overlap with the variadic kinds proposal?
  • So the ...G0 in the compose<V0, ...G0, T1> part is made possible in that proposal. I think what we'd like to propose enabling here is the f0<...G0> part. What's new about this in the first place seems to be the ability to capture generics at all, rather than using variadics (although realistically, this is a follow-up proposal that depends on it, unless you already know the generics-arity of your input function).
  • If passing generics works by reference, then there'd also be 'injecting' generics with spreads rather than just capturing them, e.g. the <...G0>(v0: V0) => T1; in the result type. I'm not even sure if that'd already be enabled by the variadic kinds proposal, but it seemed out of scope there.

What's your take there, @Igorbek, also in relation to your originally proposed notation here?

Edit: added an alternative.

[jesseschalken]

See https://github.com/Microsoft/TypeScript/issues/9949 which uses const flip = f => (a, b) => f(b, a); as an example (which is basically the same).

I would rather that TypeScript inferred the genericity of an expression without all the extra syntax, the same way that Haskell and some other functional programming languages do.

To take this example from the OP:

const wrap = f => (a, b) => f(a, b);
const pair = (a, b) => [a, b];

with types

const wrap: <A, B, C>(f: (a: A, b: B) => C): (a: A, b: B) => C;
const pair: <T>(a: T, b: T) => [T, T];

(ignore that pair should have two type parameters instead of one)

When TypeScript sees wrap(pair), it has to unify (a: A, b: B) => C (parameter to wrap) with <T>(a: T, b: T) => [T, T] (type of pair). At this point, TypeScript doesn't have any information for the type parameter T, so it just fills it with {} and keeps going, yielding (a: {}, b: {}) => [{}, {}].

TypeScript could just carry the type parameters forward without any new syntax, so instead of filling T with {}, it adds T to a list of unbound type variables, creating type assignments A = T, B = T, C = [T, T], and then uses the list of unbound type variables (T) as new type parameters, yielding <T>(a: T, b: T) => [T, T].

[KiaraGrouwstra]

@jesseschalken: Yeah, I'd take that any day. AFAIK the TS team would also prefer proposals that don't add further syntax (which just keeps adding up), so yours should be preferable. I guess that'd align with my original thread as well, where I'd also rather considered it a bug than something that should require a different notation / new syntax.

Edit: fixed link

[zpdDG4gta8XKpMCd]

@jesseschalken

TypeScript could just carry the type parameters forward

isn't it just common sense?

one can't just "resolve" unspecified type parameters by {} at whim and call it a day, can they?

dang, i am so angry

[KiaraGrouwstra]

I hope we could get any comments on this by a member; I haven't really looked at the TS code-base much, and would have use for pointers on where one might begin in order to investigate this. This fillSignature function in the parser looked vaguely relevant to me, but I'm pretty unqualified here...

[zpdDG4gta8XKpMCd]

from my experience it takes a full time job to keep up with the TS team i worked on a linter of my own based on the public API of TS, it gets outdated (stops compiling) every couple of weeks, it takes up to a day to bring it back to life and make sure all tests pass all in all in order to make a relevant feature and support it (rebase daily) until it is merged (if ever) it might take all of your time

[KiaraGrouwstra]

Yeah, I'd definitely take your word for that.

In my attempt to type Ramda, I currently have a few fixes/features I'm very much looking forward to, but I find it frustrating to see that the team has a thousand+ outstanding issues to deal with, with threads ending up for quite a while unanswered, or labeled with "accepting PRs" while barely any outsider would even have a clue on where to start.

I understand the TS team's efforts can only scale so far, especially with so few of them and so many of us, and we can't really expect to be served by them on our whims, but I wish in order to deal with that situation they'd further empower the community on how to get started with fixing things by themselves.

As it stands, I'd dive into the compiler folder to be greeted with a couple super-long files without much of an explanation of what the file's in charge of. For all I know a file name like e.g. scanner.ts does clearly describe its responsibility to those who have written compilers before; I don't know.

But if things wouldn't improve much even if you do actually manage to make a PR, that does sound worse. :(

[gcnew]

@tycho01 You can take a look at https://github.com/Microsoft/TypeScript/issues/9949 and specifically at https://github.com/Microsoft/TypeScript/issues/9949#issuecomment-267490091. I'd like to have this feature implemented as well, so I took a stab at it and made some progress. I'll come back to my fork this week and improve the unification. Currently a lot of tests break, some because the compiler infers the functions correctly but others are simply bugs. If I manage to get it working I'll submit a PR. I hope this will get the ball rolling.

PS: I think https://github.com/Microsoft/TypeScript/issues/9949 is a prerequisite for Higher Kinded Types (https://github.com/Microsoft/TypeScript/issues/1213). The variadic types in this issue are too much of a stretch for an initial version

[jesseschalken]

FWIW, Flow seems to support this just fine.

const wrap = <A,B,C>(f:(A,B)=>C):((A,B)=>C) => (a:A,b:B) => f(a,b);
const pair = <T>(a:T,b:T): [T, T] => [a,b];

const needs_number = (x:number):void => {};

needs_number(wrap(pair)('a','b')[0]);

8: needs_number(wrap(pair)('a','b')[0]);
                ^ string. This type is incompatible with the expected param type of
6: const needs_number = (x:number):void => {};
                           ^ number

It wouldn't be able to get that error without the generic for pair() passing through wrap().

Another example:

const flip = <A,B,C>(f:(A,B)=>C):((B,A)=>C) => (b:B,a:A) => f(a,b);
const pair = <A,B>(a:A,b:B):[A,B] => [a,b];

pair(1,'1')[1].charAt(0); // ok
pair(1,'1')[0].charAt(0); // error

flip(pair)(1,'1')[1].charAt(0); // error
flip(pair)(1,'1')[0].charAt(0); // ok

flip(flip(pair))(1,'1')[1].charAt(0); // ok
flip(flip(pair))(1,'1')[0].charAt(0); // error

7: pair(1,'1')[0].charAt(0);
                  ^ property `charAt`. Property not found in
7: pair(1,'1')[0].charAt(0);
        ^ Number
9: flip(pair)(1,'1')[1].charAt(0);
                        ^ property `charAt`. Property not found in
9: flip(pair)(1,'1')[1].charAt(0);
              ^ Number
13: flip(flip(pair))(1,'1')[0].charAt(0);
                               ^ property `charAt`. Property not found in
13: flip(flip(pair))(1,'1')[0].charAt(0);
                     ^ Number

Again, it wouldn't be able to get those errors without the generic for pair() passing through flip().

Try it here.

I'll add that to the long list of things Flow gets right which TypeScript doesn't, along with variance (even for properties).

The TypeScript team has said repeatedly that their objective is not complete strictness, correctness and reliability, but that is the objective of Flow. For those who need that, like myself, it seems Flow is your real home.

[gcnew]

@jesseschalken Well, to be honest Flow is not that good either. Every time I collect stamina and frustration I try it and get disappointed pretty quickly. It has far more questionable decisions than TypeScript has and the dev experience / community are nowhere near. For me a better goal is focusing on making TS better.

See https://github.com/facebook/flow/issues/123#issuecomment-266118616

[KiaraGrouwstra]

And here I was l like, "time to ask Angular to switch!".

But okay, guess we're technically a duplicate of that 9949 thread as well. :P (just joking mods, until resolved there could be info useful for resolving this in here too!)

@gcnew: mad props for actually figuring out where to start on this... that's already pretty amazing!

[KiaraGrouwstra]

@aleksey-bykov:

dang, i am so angry

I was like, well, I imagine it wouldn't have been erased intentionally!

getErasedSignature

@gcnew: how were you testing those? I'd be curious to try as well. I tried setting my VSCode typescript.tsdk to the lib path of your branch after an npm i / gulp local there, but no dice. Willing to switch IDE if it helps.

[gcnew]

@tycho01 Yes, you have to gulp local (jake local works too) and then point typescript.tsdk to PATH_TO_FORK/built/local.

PS: I think I've fixed the old compose problem, but now I'm facing a much bigger one. I lied to the compiler that one of the two functions is not generic and its types should be treated as rigid. That's why when its type parameters should be substituted they are not and the inference becomes wrong afterwards. See the updated examples. There are other problems as well. I'm thinking of workarounds but I'm not sure whether with the current inference model it can actually be made to work.

[kujon]

TypeScript could just carry the type parameters forward without any new syntax

I think this just sums it up perfectly. It would probably require some sort of lazy type resolution.

[KiaraGrouwstra]

@kujon it appears that 9949 should cover it, if it were to ever make it in.

[mhegazy]

related to https://github.com/Microsoft/TypeScript/issues/15680

[mhegazy]

looks like the same issue as https://github.com/Microsoft/TypeScript/issues/9366.

[KiaraGrouwstra]

Fixed with #16072. Edit: Some progress now.

[KiaraGrouwstra]

@aleksey-bykov:

from my experience it takes a full time job to keep up with the TS team i worked on a linter of my own based on the public API of TS, it gets outdated (stops compiling) every couple of weeks, it takes up to a day to bring it back to life and make sure all tests pass all in all in order to make a relevant feature and support it (rebase daily) until it is merged (if ever) it might take all of your time

okay, I feel you there now. it's like, things were already like that back then?!

[helmbold]

I'm not quite sure if the type system bug that I've found is the same as the one described in this issue.

If I use the Angular EventEmitter , the type parameter seems to get lost. The following example doesn't work:

const emitter: EventEmitter<string> = new EventEmitter<string>()
const other: Observable<number> = of(1)
combineLatest(emitter, other).pipe(map<[string, number], string>(() => ""))

It produces the compiler error:

Argument of type 'OperatorFunction<[string, number], string>' is not assignable to parameter of type 'OperatorFunction<[{}, number], string>'. Type '[{}, number]' is not assignable to type '[string, number]'. Type '{}' is not assignable to type 'string'.

As you can see in the source of the EventEmitter class, it is derived from Subject<T>, so the type parameter is correctly passed to the base class.

However, if I change the declared type of my emitter constant to Subject<string> or Observable<string> everything works as expected.

Works:

const emitter: Subject<string> = new EventEmitter<string>()
const other: Observable<number> = of(1)
combineLatest(emitter, other).pipe(map<[string, number], string>(() => ""))

Works

const emitter: Observable<string> = new EventEmitter<string>()
const other: Observable<number> = of(1)
combineLatest(emitter, other).pipe(map<[string, number], string>(() => ""))

Is this the same bug as described here or should I file a new issue?

[munizart]

@Igorbek Is this still a issue? All your examples as expressible now, check this out: Playground Link

Did I miss something?