Bad type reduction between two generic functions

TypeScript Version: nightly (2.5.0-dev.20170817)

Code

declare function f1<A, B>(f: (a: A) => B): () => B;
declare function f2<A, B>(f: (a: A) => B): () => B | undefined;

// g1 :: <A, B>(f: (a: A) => B): () => B
declare const g1: typeof f1 | typeof f2;

// g2 :: <A, B>(f: (a: A) => B): () => B | undefined
declare const g2: typeof f2 | typeof f1;

Expected behavior:
Both g1 and g2 should have the same type ~~<A, B>(f: (a: A) => B): () => B | undefined~~
(<A, B>(f: (a: A) => B): () => B) | (<A, B>(f: (a: A) => B): () => B | undefined).

Edit:
Note, if unification is being used this should be an error, as B has to be equal to B | undefined. On the other hand, the signature of f2 is in some sense "more generic" than f1's, so it could be the answer. Indeed, the assignability relations work as expected:

const h1: typeof f1 = f2; // Error as expected
const h2: typeof f2 = f1; // it's fine

Edit 2:
Upon further investigation, it seems that unification is the only sensible approach. I.e. both f1 and f2 should be assignable to one another for reduction to take place. If either one is not, producing a union is the only safe option. See #17863 (comment)

The issue here is that we still use type parameter erasure when comparing signatures for identity. Once A and B are replaced with any (causing undefined to be subsumed and disappear), the signatures appear identical.

in my opinion function signatures should be banned from being manipulated like being merged in unions, making it right is a can of worms and honestly it's not at all intuitive, figuring out variance compared to that is a walk in the park

no seriously, for a start, try to come up with a simple matchParameters function as follows:

const types = ['never', 'any', 'void', 'primitive', 'object', 'array', 'tuple', 'union', 'intersection', 'signature', 'generic'];
types.map(one => types.map(another => console.log(matchParameters(one, another)));
function matchParameters(one: string, another: string): string {
   // please put your bright ideas right here
}

when done, try matchResultTypes, matchingOnlyOneParameterWhileAnotherOneIsMissing, matchParameterAgainsMultipleOverloads

I'm not sure I'm following you.

I do agree that the current reduction logic is incorrect, but function unions appear naturally when you choose and return one function between two available options. I stumble upon them every now and then while working with higher order functions that return a generic "default" handler.

I've hit this specific problem while using my parser combinator library. A simplified version is as follows:

// A parser is function that takes an input stream and returns either an error,
// or a tuple of the parsed value and the rest of the stream
interface Parser<E, T> {
    (input: string): [T, string] | E
}

// Combines parsers `p1` and `p2`, such that they are sequentially invoked and their
// results are glued together by `f`. If `p1` fails, neither `p2` nor `f` is invoked.
declare function combine<E1, E2, A, B, C>(
    p1: Parser<E1, A>,
    p2: Parser<E2, B>,
    f: (a: A, b: B) => C
): Parser<E1|E2, C>;


// A simple look-ahead combinator. If `p1` fails, the result is `Parser<never, undefined>`,
// or else it acts like `combine`.
declare function trai<E1, E2, A, B, C>(
    p1: Parser<E1, A>,
    p2: Parser<E2, B>,
    f: (a: A, b: B) => C
): Parser<E2, C | undefined>;


// Bad: `... => Parser<E1 | E2, C>`          <-- what about `undefined` ?
const test1 = Math.random() ? combine : trai;

// Bad: `... => Parser<E2, C | undefined>`   <-- what about `E1` ?
const test2 = Math.random() ? trai : combine;

I do agree it would have been best if no reduction were performed at all, as both of the above inferences are wrong for different reasons.

PS: If unifications had been used, we would have known that when a reduction had been found, it would have been correct.

my point is that there is no such thing (it seems) as a unified signature produced out of the given ones

except those few trivial cases (all given sigratures are same or subtypes of the original)

this is why i don't understand how the problem you are facing can be possibly resolved in the language

it can be easily solved by wrapping your result functions and discriminating the wrappers prior to calling

Aleksey-Bykov

Aleksey-Bykov My initial post before editing suggested that the snippet should produce an error. After that I had a thought that "assignability" may be the answer, but as you've discovered that's a treacherous path.

Now I'm completely convinced the OP's snippet should either be an error or produce a union. In both cases the type of g1 and g2 should be the same. Unfortunately, however, they are two distinct reduction results as of now.

The obvious solution is to use unification (in the Hindley-Milner sense). If there is no unifier, we can either issue an error or produce a union.

if it is a practical question you should wrap your functions in Either, if it is a theoretical question, i am afraid there is no reliable answer other than showing an error

There seem to be two code paths handling functions / consts with function signature. The code below works safely.

declare const c1: <A, B>(f: (a: A) => B) => () => B;
declare const c2: <A, B>(f: (a: A) => B) => () => B | undefined;

// r1 and r2 have the same type:
// (<A, B>(f: (a: A) => B): () => B) | (<A, B>(f: (a: A) => B): () => B | undefined)
declare const r1: typeof c1 | typeof c2;
declare const r2: typeof c2 | typeof c1;

Is it expected that consts and functions behave differently?

This has been fixed; the unions in the OP are no longer reduced.

Navigation Menu

Repository navigation

Bad type reduction between two generic functions #17863

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Bad type reduction between two generic functions #17863

Description

Activity

ahejlsberg commented on Aug 18, 2017

zpdDG4gta8XKpMCd commented on Aug 28, 2017

zpdDG4gta8XKpMCd commented on Aug 28, 2017

gcnew commented on Aug 28, 2017

zpdDG4gta8XKpMCd commented on Aug 28, 2017

gcnew commented on Aug 28, 2017

zpdDG4gta8XKpMCd commented on Aug 28, 2017

gcnew commented on Aug 28, 2017

RyanCavanaugh commented on Sep 18, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions