Typescript: Improve type inference for generic curried functions

Created on 5 Apr 2017 · 25Comments · Source: microsoft/TypeScript

// #-------------- This works

type Repeat = (n: number) => (s: string) => string;
export const repeat: Repeat = n => s => s.repeat(n); // Sweet! s and n are both inferred!

// -------------------------#


// #----- Problems begin here

type Repeat2 = (n: number) => <T extends { repeat(n: number): T }>(repeatable: T) => T;

// Only n is inferred as number. Won't work with noImplicitAny enabled
export const repeat2Broken: Repeat2 = n => r => r.repeat(n); 
// Workaround is to redeclare everything from the type signature
export const repeat2Ugly: Repeat2 =
    n => <T extends { repeat(n: number): T }>(r: T) => r.repeat(n);

// -------------------------#


// #----------- It gets worse

// Type inference breaks for all args following the generic one, so even if you use
// the workaround, the next args won't regain inference
type Repeat3 = 
    (n: number) 
    => <T extends { repeat(n: number): T }>(repeatable: T) 
    => (reverse: boolean) 
    => T;

// Even if you explicitly provide the boilerplate for the generic arg, the boolean arg 
// won't be inferred. So the following won't work with noImplicitAny enabled
export const repeat3UglyAndBroken: Repeat3 =
    n => <T extends { repeat(n: number): T }>(r: T) => b => { ... }

// You have to add typing for the last arg
export const repeat3Uglier: Repeat3 =
    n => <T extends { repeat(n: number): T }>(r: T) => (b: boolean) => { ... }

// -------------------------#

I'd really appreciate better support for good inference in this kind of scenario, whether it is solved by supporting partial generic application or addition of participation of return-types in inference or whatever.

JS libraries that use a functional programming paradigm often end up loosely or any-ly typed, because you find yourself fighting the type system and adding repetitive type noise all over your code to derive any safety. A couple of examples where better support for FP would be useful:

Libraries like React or Apollo make use of curried higher-order functions for solving cross-cutting concerns. In-fact, my original use case comes from React higher-order components
Popular FP libraries like Ramda become tedious to use in a noImplicitAny project because any generic functions passed or received from the library tend to quickly devolve into {} unless you repeatedly hand-hold the type system

Here is my original use-case, if interested:

export type GetState<TState> = () => TState;
export type SetState<TState> = (newState: TState) => void;
export type StatelessComponent<TProp> = (prop: TProp) => React.ReactElement<TProp>
export type StatefulComponent<TProp, TState> = 
    (stateAccess: { getState: GetState<TState>, setState: SetState<TState> })
    => StatelessComponent<TProp>;

type ScrollableHOC = 
    (options: ScrollableOptions) 
    => <T extends ScrollableProps>(Child: ReactComponent<T>) 
    => StatefulComponent<T, ScrollableState>;

// The introduction of the Child arg breaks type inference for getState, setState, props
const scrollable: ScrollableHOC = opts => Child => ({ getState, setState }) => props => {
    // ...
}

Duplicate

Source

masaeedu

Most helpful comment

This earliest report of this issue that I know of is https://github.com/Microsoft/TypeScript/issues/9366. I've tried to implement a prototype solution using a Hindley-Milner style constraint solver, however I hit on several major problems:

TypeScript has unconstrained union types (i.e. a union may be created between any two types). When unifying two unions, you don't really know which type var with which other one "should" unify. This means that either you have to try all solutions (backtracking, very expensive) or not supporting it at all. It turns out that it's getting used in existing user code and the currently implemented approach somewhat works. This means that the new implementation should be at least as powerful. A property I wasn't able to achieve.
Error reporting. The current error reporting is very good. Languages using Hindley-Milner (especially Haskell) are known for their verbose and unhelpful messages. I couldn't figure out a way to keep the quality of the current errors, however, I do believe there are ways to come close.
Inference. The current inference algorithm leaves a lot to be desired. For example, currently "contextually typed" functions are typed by inferring the rest of the expression, and then a second pass is made using the resulting type to check the contextually typed function. A better approach would be to infer a generic signature for the contextually typed function and allow unification to do its magic. Unfortunately, inferring a generic signature of a function is impeded by mutability, need for 'var arg' types and other constraints.

All in all, it's a difficult problem. Unless the team prioritises it and puts considerable effort into figuring it out, I don't think it could be resolved.

PS: If interested, you can see my work at https://github.com/gcnew/TypeScript/tree/polyFuncUnification. I tried many approaches, not all of which committed, thus I'm not sure how well the latest commit is working.

gcnew on 6 Apr 2017

❤2 👍2

All 25 comments

It does not need a high order function to produce the behavior. Type inference fails when generic bound occurs.

type GenBound = <T extends string>(r: T) => T
var firstOrder: GenBound = r => r.length

https://www.typescriptlang.org/play/index.html#src=type%20GenBound%20%3D%20%3CT%20extends%20string%3E(r%3A%20T)%20%3D%3E%20T%0D%0Avar%20firstOrder%3A%20GenBound%20%3D%20r%20%3D%3E%20r.length

HerringtonDarkholme on 6 Apr 2017

@HerringtonDarkholme This is a contrived example to demonstrate type inference degradation when generics are involved. The request is to make type inference work for Haskell-style curried functions, I don't actually care about the Repeatable example here or how else it could be implemented.

The actual use case is React higher order components, as illustrated in the second snippet. As the name suggests, they necessarily involve higher-order functions.

masaeedu on 6 Apr 2017

@masaeedu My point here is that the root cause of this problem is not curried function but generic.

Note the spec has already said:

A contextual signature S is extracted from a function type T as follows:
If T is a function type with exactly one call signature, and if that call signature is non-generic, S is that signature.

https://github.com/Microsoft/TypeScript/blob/02547fe664a1b5d1f07ea459f054c34e356d3746/doc/spec.md#410-function-expressions

So this works as intended. Yet, TypeScript has changed a lot since 1.8. It is not impossible to change the spec.

HerringtonDarkholme on 6 Apr 2017

@HerringtonDarkholme I understand. This isn't a request for a specific change to type system's behavior. I'm simply trying to illustrate how a common use-case (defining curried functions with out-of-band type signatures) quickly becomes very tedious with the way the type system works right now.

masaeedu on 6 Apr 2017

TypeScript has unconstrained union types (i.e. a union may be created between any two types). When unifying two unions, you don't really know which type var with which other one "should" unify. This means that either you have to try all solutions (backtracking, very expensive) or not supporting it at all. It turns out that it's getting used in existing user code and the currently implemented approach somewhat works. This means that the new implementation should be at least as powerful. A property I wasn't able to achieve.
Error reporting. The current error reporting is very good. Languages using Hindley-Milner (especially Haskell) are known for their verbose and unhelpful messages. I couldn't figure out a way to keep the quality of the current errors, however, I do believe there are ways to come close.
Inference. The current inference algorithm leaves a lot to be desired. For example, currently "contextually typed" functions are typed by inferring the rest of the expression, and then a second pass is made using the resulting type to check the contextually typed function. A better approach would be to infer a generic signature for the contextually typed function and allow unification to do its magic. Unfortunately, inferring a generic signature of a function is impeded by mutability, need for 'var arg' types and other constraints.

All in all, it's a difficult problem. Unless the team prioritises it and puts considerable effort into figuring it out, I don't think it could be resolved.

gcnew on 6 Apr 2017

❤2 👍2

@gcnew I really appreciate the work that must have gone into this investigation. You're probably better equipped to determine whether this is feasible than I am, but I was wondering whether something like F#'s automatic generalization would be possible for function signatures in TypeScript. The idea is simply to infer an implicit generic type parameter for any parameters. So that when I write:

    function f(foo, bar) {
        return foo;
    }

What actually gets recorded in the type system is:

    function f<T1, T2>(foo: T1, bar: T2) {
        return foo;
    }

instead of:

    function f(foo: any, bar: any) {
        return foo;
    }

If this were the case, getting inference to work in the scenario I described above would simply involve the type checker matching up the constraints on type parameters.

masaeedu on 12 Apr 2017

It's actually very hard. You'd like these generics to be reduced to concrete types based on usage and that's far from trivial. You have to factor in overloads, mutability, variadic functions, open-ended objects, unions, subclassing, etc. If you give up on overloads, mutability and unconstrained unions (limit them to only predefined Tagged Unions (ADTs)) it becomes manageable.

gcnew on 13 Apr 2017

@RyanCavanaugh commented on the issue yesterday, see the discussion on https://github.com/Microsoft/TypeScript/issues/15114.

gcnew on 13 Apr 2017

@gcnew The scenario I'm interested in is not really usage-site, i.e. I don't really care about inference of the type args when doing foo(a, b) (although you'd get much better inference there for free). The linked issue, for example, wants to infer type information based on usage of parameters in the body of the function, whereas the change I'm proposing doesn't involve any analysis of parameter usage. What I want is to fix inference when assigning a function to a variable of a particular function type.

You are right that overloading makes things hairier (as it does in nearly every feature). Could you provide an example of how unconstrained unions/mutability would interact with the proposed change? E.g. if the following:

function foo(a, b, c) {
}

simply desugared to:

function foo<T1, T2, T3>(a: T1, b: T2, c: T3) { }

How would unions and mutability affect this?

masaeedu on 13 Apr 2017

@gcnew What I'm suggesting seems to be a dupe of #14078

masaeedu on 13 Apr 2017

I think https://github.com/Microsoft/TypeScript/issues/3410 is the first issue stating the bug. There are many related issues, but the most important ones are https://github.com/Microsoft/TypeScript/issues/5616 and https://github.com/Microsoft/TypeScript/issues/8397. The root cause of the problem is stated here: https://github.com/Microsoft/TypeScript/issues/3410#issuecomment-111646173.

gcnew on 14 Apr 2017

I think there is another usecase if it helps :

interface A
{
    add<T>(name: string, a: T, cb: TypedCallback<T>)
}

interface B
{
    add<T, U>(name: string, a: T, cb: Callback<T, U>)
}

type TypedCallback<T> = <U>(a1: T, a2: U) => void;
type Callback<T, U> = (a1: T, a2: U) => void;

var a: A, b: B;

a.add('a', { prop1: 'string' }, function (a1, a2)
{

})
b.add('b', { prop1: 'string' }, function (a1, a2)
{

})

in the case b, everything works as expected, but in case a, a1 is not inferred.

npenin on 3 May 2017

looks like a duplicate of https://github.com/Microsoft/TypeScript/issues/5616

mhegazy on 18 May 2017

@mhegazy If you look at @JsonFreeman's comment in #3410, it turns out that these are two different, but somewhat closely related problems. This issue is about improving contextual typing of function expressions by generic function signatures. The issue you linked to is about tightening up function assignability rules. They are not duplicates.

masaeedu on 18 May 2017

I am trying to prune the issues around this area. there are too many related issues.. there seems to be two categories:

here is my list so far:

composition and higer kinded-function inference (creating new type paramters)

Inference from return type position

Comparing generic signatures

open:

closed:

mhegazy on 18 May 2017

OK, i think the right one to dupe this against is https://github.com/Microsoft/TypeScript/issues/15680. though there is overlap with other issues listed above.

mhegazy on 18 May 2017

@mhegazy Yup, that seems more similar to this one.

masaeedu on 18 May 2017

@mhegazy FYI, looks like this is fixed by #16072. The example above doesn't cause errors with noImplicitAny in [email protected]. 🙌

masaeedu on 9 Jun 2017

@mhegazy, I would open an issue, but after I saw how many other issues of the same subject, even after not finding any issue about this specific case, I'll just ask here...

In this second example (const b), the generic parameter T of Array couldn't be inferred from the chained method call (fill in this case)?

const a = Array("x", "x"); // infer string[]
const b = Array(2).fill("x"); // infer any[], couldn't infer string[] ?

The most similar issue that I found was #17428, but I think that it is not the same...

lmcarreiro on 20 Nov 2017

@lmcarreiro It's not an Array<T>, it's an array of an unspecified type which a side effect happened to fill with "x"s. fill isn't the same as map, it mutates the original array. If you did Array(2).fill().map(() => "x"); you'd get string[] as you expect.

If you want a general type system where const b = Array(2); b.fill("x") organically turns b into a string[], you need to start doing whole program analysis and reasoning about all effects that may somehow touch values before you can ascribe types to the corresponding terms. This is difficult to, often results in cases where there is no "correct thing to do", and has large performance costs.

Even if you bite the bullet on the costs of that, it is still a judgement call. What if the person actually intended b in const b = [1, 2, 3]; b.fill("foo") to be an array of numbers, and accidentally filled it with the wrong type? They would expect a type error here, not a thumbs up from the type checker.

masaeedu on 20 Nov 2017

But I don't wanna turn Array<T>.fill(value: T) into Array<T>.fill<U>(value: U): U[], I know that fill mutates the original array. I'll try to explain in another example:

interface ArrayConstructor {
    // ...
    //there are these two options of constructor that takes only one parameter
    (arrayLength?: number): any[]; //option (A)
    <T>(arrayLength: number): T[]; //option (B)
    // ...
}

// here, it doesn't have enough information to match option (B), it needs to match
// option (A) and use any[] in the assign statement
const a = Array(2);
a.fill("x").fill(1); //both calls here would work because "const a" is any[]

//but here, at the same statement, it does have the information it needs to match to option (B).
//would it be too difficult to infer that T is string and match to option (B)?
const b = Array(2).fill("x");

//and here, the second call to fill method would emit an error
const c = Array(2).fill("x").fill(1);

lmcarreiro on 20 Nov 2017

@lmcarreiro It doesn't have enough information to match option B. The fill you're doing is a side effect; it is something that mutates the original array. The portion of the program being analyzed when ascribing a type to the array is Array(2), nothing else. Applying fill on top of this will only return the already fixed type of this original array, i.e. Array<any>. Similarly, ["foo"].fill(10) will produce a type error, instead of modifying the type of the original array.

If you want side effects like fill to affect the type ascribed to an object they modify, you will in the general case need to scan the entire enclosing scope for relevant side effects. Moreover, if you want things like "only the first side effect should be allowed", as shown in your last line of code, you will need to work out some notion of ordering for these side effects.

There is no way to generalize the logic you're suggesting; if I do const b = Array(2); Math.random() > 0.5 ? b.fill("x") : b.fill(1);, you would need the type of b become a probabilistic superposition of strings and numbers.

masaeedu on 20 Nov 2017

@masaeedu, you don't understand what I meant...

If you want side effects like fill to affect the type ascribed to an object they modify

That is NOT what I want, my suggestion still keeps the statically typed nature of TypeScript

The portion of the program being analyzed when ascribing a type to the array is Array(2), nothing else

That is what I meant to change, try to use the whole assignment statement to infer the type, NOT the whole function body, example:

const c = Array(2).slice(0, 1).fill("x").fill(1); infer string[], do NOT infer number[]

Trying to infer T of <T>(arrayLength: number)

Try to infer T from Array(2): fail
Try to infer T from Array(2).slice(0, 1): fail
Try to infer T from Array(2).slice(0, 1).fill("x"): success, T of (T[]).fill(value: T): T[] is string. Stop HERE, do NOT analyse the rest of the statement (.fill(1) in this example).

So, the .fill(1) call would get an error.

It will assign any type to T only after check the whole assignment statement. It would not check the code after the assignment. In this case let b = Array(2); b = b.fill(1); the const b would still be any[] because the .fill(1) call is in another statement and b were already inferred to any[] type.

lmcarreiro on 20 Nov 2017

It will assign any type to T only after check the whole assignment statement

Special casing assignment statements in a language like JS is not a good idea. An assignment statement may contain any number of other things, up to and including entire function expressions, more assignment expressions, narrowing blocks, and picking the "first winner" in such a tree is far from obvious.

Whatever logic you propose needs to obey some modicum of equational reasoning. If I do const y = Array(2).fill(...), I would expect the ascribed types to match const x = Array(2); const y = x.fill(...). The existing logic sensibly obeys this: const y = Array(2).fill().map(() => 10) is equivalent to const x = Array(2).fill(); const y = x.map(() => 10).

masaeedu on 20 Nov 2017

To put it another way, expressions should stay abstract wrt their type parameters as long as possible (instead of turning into any), and usage of the abstractly typed term in a context should reify the contextual expression. If I have a <T>(x: T) => T and apply it to a U, it shouldn't retroactively change the type of the <T>(x: T) => T expression; it should ensure that the result of the application expression is U. The alternative nonsensical behavior is similar to what Flow does, which is greatly annoying.