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

[benlesh]

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]

FWIW, this appears to work in FlowType

[buzzdecafe]

There's no "b" in ramda

[Igorbek]

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.

[DanielRosenwasser]

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]

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]

@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.

[KiaraGrouwstra]

@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]

@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]

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?

[KiaraGrouwstra]

@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]

@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]

Thanks for the detailed explanation!