Trouble typing a sum type with generics and overloads

Question

I am trying to type an implementation of Either and I struggle to make the two variants play well with each other.

First, the implementation:

type Unary<X, R> = (x: X) => R;
type Either<L=unknown, R=unknown> = Left<L> | Right<R>

class Right<R=unknown> {
    constructor (private value: R) {}

    static of <T>(value:T):Right<T> { return new Right(value); }

    map <U>(f:Unary<R, U>):Right<U> {
        return Right.of(f(this.value));
    }

    ap <T>(either: Left<T>): Left<T>
    ap <U>(either: Right<Unary<R, U>>): Right<U>
    ap <T, U>(either: Either<T, Unary<R, U>>): Either<T, U> {
        return either instanceof Left
            ? either
            : this.map(either.value);
    }
}

class Left<L=unknown> {
    constructor (private value: L) {}

    static of <T>(value:T):Left<T> { return new Left(value); }

    map (_:Function): Left<L> { return this; }

    ap <T>(either: Left<T>): Left<T>
    ap (either: Right): Left<L>
    ap (either: Either): Left { 
        return either instanceof Left ? either : this;
    }
}

On the surface, everything appears to be working fine both at runtime and compile time:

const r1 = Right.of(1);
const r2 = Right.of(2);
const l1 = Left.of(Error('foo'));
const l2 = Left.of(Error('bar'));

const add = (a:number) => (b:number) => a + b

// Right { value: 3 } : Right<number>
const rr = r2.ap(r1.map(add));

// Left { value: [Error: foo] } : Left<Error>
const lr = r2.ap(l1.map(add));

// Left { value: [Error: bar] } : Left<Error>
const rl = l2.ap(r1.map(add));

// Left { value: [Error: foo] } : Left<Error>
const ll = l2.ap(l1.map(add));

...but it falls apart if I try to define a lift function.

const lift2 = <A, B, R>(f:(a: A) => (b: B) => R) => {
    function lifted(a:Right<A>, b:Right<B>): Right<R>
    function lifted<U>(a:Right<A>, b:Left<U>): Left<U>
    function lifted<T>(a:Left<T>, b:Right<B>): Left<T>
    function lifted<T>(a:Left<T>, b:Left): Left<T>
    function lifted(a: Either, b: Either):Either {
        return b.ap(a.map(f));
        //          ------=-
    }
    return lifted;
}

I have 2 distinct errors

Argument of type 'Left<unknown> | Right<(b: B) => R>' is not assignable to parameter of type 'Left<unknown>'.
  Type 'Right<(b: B) => R>' is not assignable to type 'Left<unknown>'.
    Types have separate declarations of a private property 'value

The call would have succeeded against this implementation, but implementation signatures of overloads are not externally visible.

Argument of type '(a: A) => (b: B) => R' is not assignable to parameter of type 'Unary<unknown, (b: B) => R> & Function'.
  Type '(a: A) => (b: B) => R' is not assignable to type 'Unary<unknown, (b: B) => R>'.
    Types of parameters 'a' and 'x' are incompatible.
      Type 'unknown' is not assignable to type 'A'.
        'A' could be instantiated with an arbitrary type which could be unrelated to 'unknown'

Oddly enough, the correct types are inferred on the call site:

const add = lift2(
    (a:number) => (b:number) => a + b
);

// Right { value: 3 } : Right<number>
const rr = add(r1, r2);

// Left { value: [Error: foo] } : Left<Error>
const lr = add(l1, r2);

// Left { value: [Error: bar] } : Left<Error>
const rl = add(r1, l2);

// Left { value: [Error: foo] } : Left<Error>
const ll = add(l1, l2);

I don't know why Left<unknown> is inferred for the type parameter
I don't know where the unknown in Unary<unknown, (b: B) => R> comes from

jcalz jcalz · Accepted Answer · 2021-04-21T19:25:00

First of all, I'd suggest making the implementation signature of lifted() more precise... perhaps something like this:

function lifted<T, U>(
  a: Either<T, A>, 
  b: Either<U, B>
): Either<U, R> | Left<T> {...};

This should make any problems involving unknown go away... your original types for a and b were just Either which is Either<unknown, unknown> (thanks to generic type parameter defaults), and the compiler is right to complain that you can't pass unknown to something that expects an A.

In fact, I'd suggest making the full set of signatures as precise as possible, and not let unknown creep in anywhere it doesn't need to:

    function lifted(a: Right<A>, b: Right<B>): Right<R>
    function lifted<U>(a: Right<A>, b: Left<U>): Left<U>
    function lifted<T, U>(a: Left<T>, b: Either<U, B>): Left<T>
    function lifted<T, U>(a: Either<T, A>, b: Either<U, B>): Either<U, R> | Left<T> {
        // impl to come
    }
    return lifted;

Next, the compiler is not smart enough to see that b.ap(a.map(f)) is correct, because it treats a and b as two Either types, which are unions. And while it turns out that b.ap(a.map(f)) will always work no matter whether a or b is Left or Right, there is no single call signature for Either.map or Either.ap which is obviously correct to the compiler. Either is a union type, and its ap and map methods are therefore unions of functions... and overloaded functions, to boot. The compiler cannot resolve call signatures in an intelligent way for all these unions-of-overloads. This is similar to the problem I have with what I've been calling correlated union types (see microsoft/TypeScript#30581).

If the compiler were to re-evaluate b.ap(a.map(f)) for each of the four possibilities for a and b, it would be happy with each one. But since you only have one line, the compiler only considers it one time. There is no such thing as "control flow analysis which distributes over unions" (see microsoft/TypeScript#25051 for a closed request for such functionality, which would fix this if it were implemented.)

Without such abilities, you have two basic options:

1: use something like type assertions to just tell the compiler not to worry about type safety for that line, for example:

return (b as any).ap(a.map(f)); // uses any here

This places the burden of type safety on you, so you need to be careful. It is the most convenient option, though.

2: use redundant code to walk the compiler through the different possibilities for which it is able to verify type safety:

const aMapF = a.map(f);
return aMapF instanceof Left ? b.ap(aMapF) :
  b instanceof Left ? b.ap(aMapF) :
    b.ap(aMapF);

This is completely type safe, and the compiler sees that because control flow analysis allows narrowing of union-typed things to singly-typed things. Of course, you pay for this safety with redundantly repetitive redundancy.

Playground link to code

Trouble typing a sum type with generics and overloads

1 Answers