Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Smarter type inference for functional programming (RxJS, Ramda, etc) #15680

Closed
benlesh opened this issue May 8, 2017 · 12 comments

Comments

@benlesh
Copy link

commented May 8, 2017

EDIT: updated the types in example to match what works perfectly in Flow type

TypeScript Version: 2.2.1 / nightly (2.2.0-dev.201xxxxx)

TypeScript is unable to infer types through higher-order functions.

Code

Given some imaginary class SetOf, which is just some set of values we want to compose operations over... We'll try the following:

// This is a contrived class. We could do the same thing with Observables, etc.
class SetOf<A> {
  _store: A[];

  add(a: A) {
    this._store.push(a);
  }

  transform<B>(transformer: (a: SetOf<A>) => SetOf<B>): SetOf<B> {
    return transformer(this);
  }

  forEach(fn: (a: A, index: number) => void) {
      this._store.forEach((a, i) => fn(a, i));
  }
}

function compose<A, B, C, D, E>(
  fnA: (a: SetOf<A>) => SetOf<B>, 
  fnB: (b: SetOf<B>) => SetOf<C>, 
  fnC: (c: SetOf<C>) => SetOf<D>,
  fnD: (c: SetOf<D>) => SetOf<E>,
):(x: SetOf<A>) => SetOf<E>;
/* ... etc ... */
function compose<T>(...fns: ((x: T) => T)[]): (x: T) => T {
  return (x: T) => fns.reduce((prev, fn) => fn(prev), x);
}

function map<A, B>(fn: (a: A) => B): (s: SetOf<A>) => SetOf<B> {
  return (a: SetOf<A>) => {
    const b: SetOf<B> = new SetOf();
    a.forEach(x => b.add(fn(x)));
    return b;
  }
}

function filter<A>(predicate: (a: A) => boolean): (s: SetOf<A>) => SetOf<A> {
  return (a: SetOf<A>) => {
    const result = new SetOf<A>();
    a.forEach(x => {
      if (predicate(x)) result.add(x);
    });
   return result;
  }
}

const testSet = new SetOf();
testSet.add(1);
testSet.add(2);
testSet.add(3);

// THE PROBLEM IS HERE
// all functions below are unable to infer any types.
// The user will be required to annotate the types manually at each step.
testSet.transform(
  compose(
    filter(x => x % 1 === 0),
    map(x => x + x),
    map(x => x + '!!!'),
    map(x => x.toUpperCase())
  )
)

testSet.transform(
  compose(
    filter(x => x % 1 === 0),
    map(x => x + x),
    map(x => 123),  // Whoops a bug
    map(x => x.toUpperCase()) // causes an error!
  )
)

Libraries Where This Problem Will Exist

RxJS

We want to move RxJS over to using "lettable operators". That means operators that are built in a similar fashion to what you see in the example able. The current prototype augmentation is untenable for large applications, and makes tree-shaking hard if not impossible with regards to Rx.

Ramda

A widely popular functional programming library will undoubtedly have the same issues. Especially give that (I think) the compose function shown above exists (probably in a better form) within Ramdba.

Redux

combineReducers in redux is liable to have this same problem, at least when dealing with typed reducers. I don't think the reducer's types can be inferred inside of that call. However, I'm not sure it's a common use case for Redux to have inline reducers in a combineReducers call.

Plain JavaScript

This problem would exist for any higher-order function used in this manner within JavaScript:

// given the same `compose` function from above:

const result = [1, 2, 3, 4].map(
  compose(
    x => x + x,
    x => x + '!!!',
    x => parseInt(x)
  )
);

console.log(result); // [2, 4, 6, 8]

cc/ @rkirov @IgorMinar @david-driscoll @alexeagle

@benlesh

This comment has been minimized.

Copy link
Author

commented May 8, 2017

@buzzdecafe

This comment has been minimized.

Copy link

commented May 8, 2017

There's no "b" in ramda

@Igorbek

This comment has been minimized.

Copy link
Contributor

commented May 8, 2017

I think TS cannot infer generic types only. If you pass concrete types to compose (functions that are not generic), TS will infer types properly. But it lacks inference when arguments are generic themselves.

That problem was discussed a little bit here #10247. @gcnew even made a prototype where a generic parameters can be introduced by the arguments in such compositions.

@benlesh benlesh changed the title Smarter type inference for functional programming (RxJS, Rambda, etc) Smarter type inference for functional programming (RxJS, Ramda, etc) May 9, 2017

@DanielRosenwasser

This comment has been minimized.

Copy link
Member

commented May 9, 2017

I do think that @Igorbek's issue is the same as this one. We may choose to consolidate on the two.

I have been thinking about this problem for a while and would really like for us to improve here.

@benlesh

This comment has been minimized.

Copy link
Author

commented May 9, 2017

I've updated the example above a little bit, but the spirit is the same.

This is a feature RxJS dearly needs in order to have solid TypeScript support with the direction we'd like to go. A direction the Angular team has expressed interest in us going as well.

@benlesh

This comment has been minimized.

Copy link
Author

commented May 9, 2017

@DanielRosenwasser ... is it safe to say improvements around this are on your roadmap? Because it will affect long-term decisions that the RxJS team makes.

@tycho01

This comment has been minimized.

Copy link
Contributor

commented May 12, 2017

@benlesh:

[Ramda] will undoubtedly have the same issues.

Yeah, most user-reported issues there (and a bunch of failing tests) boil down to this one bug. Minimum repro is R.pipe(R.identity) (or R.compose, though argument order makes that one worse). As shown in @Igorbek's thread, it erases the generics to {}. It seems @gcnew did make good progress on his branch, so hopefully that could make it in.

@billba

This comment has been minimized.

Copy link
Member

commented May 24, 2017

@benlesh in your example I think maybe you need:

const testSet = new SetOf<number>();`

Was just preparing to file basically the same issue, but as usual you are exactly 16 days ahead of me.

@OliverJAsh

This comment has been minimized.

Copy link

commented Jun 10, 2017

Using typescript@next today, the example in the original post now works:

{
    function compose<A, B, C>(
        f: (x: A) => B,
        g: (x: B) => C
    ): (x: A) => C {
        return x => g(f(x));
    }

    const result = [1, 2, 3, 4].map(
        compose(
            x => x + '!!!',
            x => parseInt(x)
        )
    );

    console.log(result); // [2, 4, 6, 8]
}

However, the definition of compose here is not one usually seen in libraries such as Ramda. The compose above flows from left to right, whereas usually compose flows from right to left. When doing so, TypeScript loses inference of the generic. For example:

{
    function compose<A, B, C>(
        g: (x: B) => C,
        f: (x: A) => B,
    ): (x: A) => C {
        return x => g(f(x));
    }

    const result = [1, 2, 3, 4].map(
        compose(
            x => parseInt(x), // error: Argument of type '{}' is not assignable to parameter of type 'string'.
            x => x + '!!!',
        )
    );

    console.log(result); // [2, 4, 6, 8]
}

Is there any way we can fix this?

@tycho01

This comment has been minimized.

Copy link
Contributor

commented Jun 10, 2017

@OliverJAsh: thanks for mentioning that; I guess it got sorta overlooked in my links above.
It seems @gcnew was still experiencing issues as well.

@ahejlsberg

This comment has been minimized.

Copy link
Member

commented Jun 10, 2017

@OliverJAsh This is a consequence of inference working left-to-right for contextually typed arguments. To solve it in the general case would require some form of unification, but that might in turn uncover other issues as has been @gcnew's experience.

I should add that in my experience APIs where information flows left-to-right are much more intuitive and ergonomic. It becomes evident when you look at the experience someone would have with the "backwards" form of compose when actually authoring the code. Say you're typing and you've gotten this far:

const result = [1, 2, 3, 4].map(
    compose(
        x => x.

With the original form of compose we can provide a completion list here because enough information to infer a type for x is present in the code already. But in the backwards case we can't know the type of x until you write the second argument, so we've got nothing to go on.

@OliverJAsh

This comment has been minimized.

Copy link

commented Jun 10, 2017

Thanks for the detailed explanation!

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
9 participants
You can’t perform that action at this time.