Why one of my compose functions cannot infer types?

Question

I have 2 composing functions: compose and composeR. They receive 2 functions and compose them together in a way that, output of one function is passed as an input to another function. This is their definitions:

type Compose = <A, B, C>(
  f: (x: B) => C, 
  g: (x: A) => B
) => (x: A) => C
const compose: Compose = 
  (f, g) => x => f(g(x))

type ComposeR = <A, B, C>(
  g: (x: A) => B
  f: (x: B) => C, 
) => (x: A) => C
const composeR: ComposeR = 
  (g, f) => x => g(f(x))

Now trying to compose functions like below, everything compiles and all the types are inferred correctly:

type Increment = (x: number) => number
const increment: Increment = x => x+1

type ToString = (x: number) => string
const toString: ToString => x => `${x}`

const composed = compose(toString, increment)
const composedR = compose(increment, toString)
composed(12)   // "13"
composedR(12)   // "13"

But if I try more complex input functions, I get into compile issue for compose() function:

type Option<A> = Some<A> | None

interface Some<A> {
  _tag: 'Some'
  value: A
}

interface None {
  _tag: 'None'
}

const some = <A,>(x: A): Option<A> => 
  ({ _tag: 'Some', value: x })

const none: Option<never> = 
  { _tag: 'None' }

const isNone = <A,>(x: Option<A>): x is None => 
  x._tag === 'None'

// --------------------

type Either<E, A> = Left<E> | Right<A>

interface Left<E> {
  _tag: 'Left'
  left: E
}

interface Right<A> {
  _tag: 'Right'
  right: A
}

const left = <E,A=never>(x: E):  Either<E, A> => ({ _tag: 'Left', left: x})
const right = <A,E=never>(x: A):  Either<E, A> => ({ _tag: 'Right', right: x})

const isLeft = <E, A>(a: Either<E, A>): a is Left<E> => 
  a._tag === 'Left'


// --------------------

interface URItoKind1<A> {
    'Option': Option<A>
}

interface URItoKind2<E,A> {
    'Either': Either<E,A>
}

type URIS1 = keyof URItoKind1<any>
type URIS2 = keyof URItoKind2<any, any>

type Kind1<URI extends URIS1, A> = URItoKind1<A>[URI]
type Kind2<URI extends URIS2, E, A> = URItoKind2<E,A>[URI]

type HKT1<URI, A> = { URI: URI; a: A }; 
type HKT2<URI, A, B> = { URI: URI; a: A; b: B }  

interface Functor1<F extends URIS1> {
    readonly URI: F
    map: <A, B>(f: (a: A) => B) => (fa: Kind1<F, A>) => Kind1<F, B>
}

interface Functor2<F extends URIS2> {
    readonly URI: F
    map: <E, A, B>(f: (a: A) => B) => (fa: Kind2<F, E, A>) => Kind2<F, E, B>
}

interface Functor<F> {
    readonly URI: F
    map: <A, B>(f: (a: A) => B) => (fa: HKT1<F, A>) => HKT1<F, B>
}

// --------------------------

const optionFunctor: Functor1<'Option'> = {
  URI: 'Option',
  map: <A,B>(f: (x: A) => B) => (fa: Option<A>): Option<B> => 
    isNone(fa) ? none : some(f(fa.value))
}

const eitherFunctor: Functor2<'Either'> = {
  URI: 'Either',
  map: <E,A,B>(f: (x: A) => B) => (fa: Either<E, A>): Either<E, B> => 
    isLeft(fa) ? fa : right(f(fa.right))
}

// ---------------------------

type Compose = <A, B, C>(
  f: (x: B) => C, 
  g: (x: A) => B
) => (x: A) => C

const compose: Compose = 
  (f, g) => x => f(g(x))

type ComposeR = <A, B, C>(
  g: (x: A) => B,
  f: (x: B) => C 
) => (x: A) => C

const composeR: ComposeR = 
  (g, f) => x => f(g(x))

// ---------------------------

type Increment = (x: number) => number
const increment: Increment = x => x+1

type ToStringg = (x: number) => string
const toStringg: ToStringg = x => `${x}`

const composed = compose(toStringg, increment)
const composedR = composeR(increment, toStringg)
composed(12)   // "13"
composedR(12)   // "13"

// This section compiles ok and types inferred correctly when composing functions.

// ---------------------------

const map1 = optionFunctor.map
const map2 = eitherFunctor.map

const composed1 = compose(map1, map2)       // <=== map2 has error and types cannot be inferred correctly
const composed2 = composeR(map1, map2)      // <=== map2 is ok here!

// Try switching map1 and map2. Why in `composed1` TypeScript cannot infer types correctly? how can I fix it?

What happens is, compose cannot infer types correctly. But if I try this with composeR() types are inferred with no issues. Why is the compose() function can't infer types correctly? How can I fix this?

• problematic sample code

Answer 1

This is considered a design limitation of TypeScript. See microsoft/TypeScript#31738.

---

TypeScript has very limited support for the sort of higher-order generic function propagation you're trying to achieve here. This support, as released in TypeScript 3.4 and implemented in microsoft/TypeScript#30215, only works in very specific circumstances, and your Compose type isn't supported.

---

According to the description of microsoft/TypeScript#30215, the higher-order function inference

is not a complete unification algorithm and it is by no means perfect. In particular, it only delivers the desired outcome when types flow from left to right. However, this has always been the case for type argument inference in TypeScript, and it has the highly desired attribute of working well as code is being typed.

In your Compose* types, you want TypeScript to synthesize a generic function (the one from A to C) by using the generic type parameters from the g input (the one from A to B) and propagating to the f input (the one from B to C).

Your ComposeR type is

type ComposeR = <A, B, C>(g: (x: A) => B, f: (x: B) => C) => (x: A) => C

and you can see that the required flow from g to f happens in the same order as the parameters. Left to right. So it works. But in Compose,

type Compose = <A, B, C>(f: (x: B) => C, g: (x: A) => B) => (x: A) => C

the required flow from g to f would have to happen in the opposite order. Right to left. So it does not work.

---

So that's why it's happening. It can't be fixed easily. Until and unless some more full-featured generic support is added to TypeScript (possibly involving higher-kinded types as discussed in microsoft/TypeScript#1213), you'll have to either give up or work around it.