Q:

Abstracting away a generic type parameter in typescript

I'm running into a situation where I can't seem to avoid any in Typescript. Here's an example that mirrors what I'm trying to do:
type NativeFn<A, B> = {
    kind: 'native'
    fn: (a: A) => B
}

type ComposeFn<A, B, C> = {
    kind: 'compose'
    f: Fn<B, C>
    g: Fn<A, B>
}

type Fn<A, B> = NativeFn<A, B>
    | ComposeFn<A, any, B>  // <=== HERE

function evalfn<A, B>(fn: Fn<A, B>, arg: A): B {
    switch (fn.kind) {
        case 'native': return fn.fn(arg)
        case 'compose': {
            // intermediate has type "any", which is a drag.
            const intermediate = evalfn(fn.g, arg)
            return evalfn(fn.f, intermediate)
        }
    }
}

What I want to say is that ComposeFn<A, B, C> is always a Fn<A, C>, no matter which type B is, but B should still be typed.
With any, I can incorrectly type things like:
const F: Fn<string, string[]> = { kind: 'native', fn: (n) => [n] }

const G: Fn<number, number> = { kind: 'native', fn: (n) => n + 1 }

const FoG: Fn<number, string[]> = {
    kind: 'compose',
    f: F,
    g: G,
}

unknown doesn't work either. Example.
Is there any way do accomplish what I'm going for here?

A:

TypeScript does not have direct support for existential types (see microsoft/TypeScript#14466).  If it did, you would use an existential type like <∃T> ComposeFn<string, T, number> to mean something like "there is some type T such that my type is ComposeFn<string, T, number>, but I don't know or care what it is":
// not valid TS syntax, do not try this
type Fn<A, B> = NativeFn<A, B> | <∃T> ComposeFn<A, T, B> 

Without direct support for such types, there are various workarounds.  The easiest one by far is to use any in place of the existential type and not worry too much.  Yes, this allows unsafe things to happen, but TypeScript isn't really a perfectly type-safe language (see microsoft/TypeScript#9825) nor is it intended to be (see TypeScript Design Non-Goal #3) and any is really very convenient.  
You might get a little extra safety by allowing Fn to specify the "existential" argument and having it default to any, like this:
type Fn<A, B, T = any> = NativeFn<A, B>
    | ComposeFn<A, T, B>

function evalfn<A, B, T>(fn: Fn<A, B, T>, arg: A): B {
    switch (fn.kind) {
        case 'native': return fn.fn(arg)
        case 'compose': {
            const intermediate = evalfn(fn.g, arg)
            return evalfn(fn.f, intermediate)
        }
    }
}

It's not perfect, but at least the compiler will complain instide evalfn if you do something too weird.

If you really want type safety, you can emulate existential types by using a generic function implementation; if I have a function signature like <T>(x: T, y: T) => void then the caller gets to choose T and the implementer needs to treat T like an existential type parameter.  By switching who's the caller and who's the implementer, it gives us a weird inside-out way to represent Fn<A, B> in a type-safe manner:
type SomeComposeFn<A, B> = {
  kind: 'compose',
  <R>(go: <T>(f: Fn<T, B>, g: Fn<A, T>) => R): R
}

type Fn<A, B> = NativeFn<A, B> | SomeComposeFn<A, B>

Here, a SomeComposeFn<A, B> is itself a function that acts sort of like a Promise for your f and g functions.  You can then implement evalfn like this:
function evalfn<A, B>(fn: Fn<A, B>, arg: A): B {
  switch (fn.kind) {
    case 'native': return fn.fn(arg)
    case 'compose': {
      return fn((f, g) => {
        const intermediate = evalfn(g, arg)
        return evalfn(f, intermediate)
      });
    }
  }
}

And if you have a value of your original ComposeFn<A, T, B> type, you can convert it into a SomeComposeFn<A, B> in a straightforward way, like resolving a promise:
function someComposeFn<A, T, B>(composeFn: ComposeFn<A, T, B>): SomeComposeFn<A, B> {
  return Object.assign(
    <R>(go: <T>(f: Fn<T, B>, g: Fn<A, T>) => R) => go(composeFn.f, composeFn.g),
    { kind: "compose" as const });
}

So that's perfectly type safe in just the way you want it, but cumbersome enough not to be the approach I'd probably choose.  Of course it's up to you, though. 

Okay, hope that gives you some direction; good luck!
Playground link to code

