search

KiaraGrouwstra / typical

playground for type-level primitives in TypeScript
MIT License
173 stars 5 forks source link

higher kinded types #22

Closed SimonMeskens closed 6 years ago

SimonMeskens commented 6 years ago

EDIT: I ended up releasing my idea as a library called TypeProps

Proof-of-concept:

type unknown = {} | null | undefined;

// Functor
interface StaticFunctor<G> {
    map<F extends Generic<G>, U>(
        transform: (a: Parameters<F>[0]) => U,
        mappable: F
    ): Generic<F, [U]>;
}

// Examples
const arrayFunctor: StaticFunctor<any[]> = {
    map: <A, B>(fn: (a: A) => B, fa: A[]): B[] => {
        return fa.map(fn);
    }
};
const objectFunctor: StaticFunctor<object> = {
    map: <A, B>(fn: (a: A) => B, fa: A): B => {
        return fn(fa);
    }
};
const nullableFunctor: StaticFunctor<object | null | undefined> = {
    map: <A, B>(
        fn: (a: A) => B,
        fa: A | null | undefined
    ): B | null | undefined => {
        return fa != undefined ? fn(fa) : fa;
    }
};

const doubler = (x: number) => x * 2;

const xs = arrayFunctor.map(doubler, [4, 2]); // xs: number[]
const x = objectFunctor.map(doubler, 42); // x: number
const xNull = nullableFunctor.map(doubler, null); // xNull: null
const xSome = nullableFunctor.map(doubler, 4 as number | undefined); // xSome: number | undefined

const functor: StaticFunctor<unknown | any[]> = {
    map(fn, fa) {
        return Array.isArray(fa)
            ? arrayFunctor.map(fn, fa)
            : fa != undefined
                ? objectFunctor.map(fn, fa)
                : nullableFunctor.map(fn, fa);
    }
};

const ys = functor.map(doubler, [4, 2]); // ys: number[]
const y = functor.map(doubler, 42); // y: number
const yNull = functor.map(doubler, null); // yNull: null
const ySome = functor.map(doubler, 42 as number | undefined); // ySome: number | undefined

// Plumbing
interface TypeProps<T = {}, Params extends ArrayLike<any> = never> {
    array: {
        infer: T extends Array<infer A> ? [A] : never;
        construct: Params[0][];
    };
    null: {
        infer: null extends T ? [never] : never;
        construct: null;
    };
    undefined: {
        infer: undefined extends T ? [never] : never;
        construct: undefined;
    };
    unfound: {
        infer: [NonNullable<T>];
        construct: Params[0];
    };
}

type Match<T> = T extends infer U
    ? ({} extends U ? any
        : TypeProps<U>[Exclude<keyof TypeProps, "unfound">]["infer"]) extends never
    ? "unfound"
    : {
        [Key in Exclude<keyof TypeProps, "unfound">]:
        TypeProps<T>[Key]["infer"] extends never
        ? never : Key
    }[Exclude<keyof TypeProps, "unfound">] : never;

type Parameters<T> = TypeProps<T>[Match<T>]["infer"];

type Generic<
    T,
    Params extends ArrayLike<any> = ArrayLike<any>,
    > = TypeProps<T, Params>[Match<T>]["construct"];
SimonMeskens commented 6 years ago

What I would really want to do, is something like this: 

interface Functor<F> {
    map: F extends Maybe<infer A> ? <B>(f: (a: A) => B) => Functor<Maybe<B>> : never
    map: F extends Array<infer A> ? <B>(f: (a: A) => B) => Functor<Array<B>> : never
}

So that you can just extend the interface of Functor with new Functor definitions. This is very similar to Haskell. Unfortunately I haven't found a way yet to make it work in TypeScript.

This works, but is not extendable:

type Functor<F> = {
    map: F extends Maybe<infer A> ? <B>(f: (a: A) => B) => Functor<Maybe<B>> :
         F extends Array<infer A> ? <B>(f: (a: A) => B) => Functor<Array<B>> :
         never
}

I think there might be a solution here, but I haven't found it just yet

SimonMeskens commented 6 years ago

I think I've got this solved! I might release typeprops as a small library, it seems really useful. Still haven't found anything that works better than providing a global interface. Intellisense is horrible, will try to fix that somehow.

Here's some complex code a friend gave me, that now works fine:

typeprops.ts:

type defined = {} | null;
type unknown = {} | null | undefined;

type Tuple = {
    [index: number]: unknown;
    length: number;
};

declare module "typeprops" {
    interface TypeProps<Type, Params extends Tuple = never> {
        never: {
            parameters: never;
            type: never;
        };
    }

    type TypeParams<T> = TypeProps<T>[keyof TypeProps<T>]["parameters"];

    type Generic<T, Params extends Tuple = TypeParams<T>> = TypeProps<
        T,
        Params
    >[keyof TypeProps<T>]["type"];
}

maybe.ts:

import { Generic } from "typeprops";

// Just :: a -> T a
// None :: T a
// match :: { "Just" :: a -> b, "None" :: b } -> T a -> b
const GenericMaybe = <F>({
    Just,
    None,
    match
}: {
    Just: <T>(x: T) => Generic<F, [T]>;
    None: F;
    match: <T, U>(
        {
            Map,
            None
        }: {
            Map: (x: T) => Generic<F, [U]>;
            None: Generic<F, [undefined]>;
        }
    ) => (o: Generic<F, [T]>) => Generic<F, [U]>;
}) => {
    const genericNone = (None as any) as Generic<F, [undefined]>;

    // Functor
    // map :: (a -> b) -> T a -> T b
    const map = <T, U>(f: (a: T) => U) =>
        match!({ None: genericNone, Map: (x: T) => Just(f(x)) });

    // Monad
    // of :: a -> T a
    const of = Just;
    // chain :: (a -> T b) -> T a -> T b
    const chain = <T, U>(f: (a: T) => Generic<F, [U]>) =>
        match!({ None: genericNone, Map: f });

    return { map, of, chain };
};

// A possible representation of a Maybe
const k = Symbol("my maybe key");
type Maybe<T> = { [k]: T | undefined };

declare module "typeprops" {
    interface TypeProps<Type, Params extends Tuple = never> {
        [k]: {
            parameters: Type extends Maybe<infer A> ? [A] : never;
            type: Type extends Maybe<any> ? Maybe<Params[0]> : never;
        };
    }
}

const Just = <T>(x: T) => ({ [k]: x } as Maybe<T>);
const None = {} as Maybe<undefined>;

const match: <T, U>(
    {
        Map,
        None
    }: {
        Map: (x: T) => Maybe<U>;
        None: Maybe<undefined>;
    }
) => (o: Maybe<T>) => Maybe<U> = <T, U>({
    Map,
    None
}: {
    Map: (x: T) => Maybe<U>;
    None: Maybe<undefined>;
}) => (o: Maybe<T>) => (o.hasOwnProperty(k) ? Map(o[k]!) : None) as Maybe<U>;

const { map, chain, of } = GenericMaybe({ Just, None, match });

// Examples
console.log([
    map((x: number) => x + 2)(of(42)),
    map((x: number) => x + 2)(None),
    chain((x: number) => (x > 40 ? None : of(x * 2)) as Maybe<number>)(of(42)),
    chain((x: number) => (x > 40 ? None : of(x * 2)) as Maybe<number>)(of(32)),
    map((x: number) => None)(of(42)),
    map((x: number) => of(x * 2))(of(42))
]);

Playground: Playground link%20%3D%3E%20(o%3A%20Generic%3CF%2C%20%5BT%5D%3E)%20%3D%3E%20Generic%3CF%2C%20%5BU%5D%3E%3B%0D%0A%20%20%7D)%20%3D%3E%20%7B%0D%0A%20%20const%20genericNone%20%3D%20(None%20as%20any)%20as%20Generic%3CF%2C%20%5Bundefined%5D%3E%3B%0D%0A%0D%0A%20%20%2F%2F%20Functor%0D%0A%20%20%2F%2F%20map%20%3A%3A%20(a%20-%3E%20b)%20-%3E%20T%20a%20-%3E%20T%20b%0D%0A%20%20const%20map%20%3D%20%3CT%2C%20U%3E(f%3A%20(a%3A%20T)%20%3D%3E%20U)%20%3D%3E%0D%0A%20%20%20%20match!(%7B%20None%3A%20genericNone%2C%20Map%3A%20(x%3A%20T)%20%3D%3E%20Just(f(x))%20%7D)%3B%0D%0A%0D%0A%20%20%2F%2F%20Monad%0D%0A%20%20%2F%2F%20of%20%3A%3A%20a%20-%3E%20T%20a%0D%0A%20%20const%20of%20%3D%20Just%3B%0D%0A%20%20%2F%2F%20chain%20%3A%3A%20(a%20-%3E%20T%20b)%20-%3E%20T%20a%20-%3E%20T%20b%0D%0A%20%20const%20chain%20%3D%20%3CT%2C%20U%3E(f%3A%20(a%3A%20T)%20%3D%3E%20Generic%3CF%2C%20%5BU%5D%3E)%20%3D%3E%0D%0A%20%20%20%20match!(%7B%20None%3A%20genericNone%2C%20Map%3A%20f%20%7D)%3B%0D%0A%0D%0A%20%20return%20%7B%20map%2C%20of%2C%20chain%20%7D%3B%0D%0A%7D%3B%0D%0A%0D%0A%2F%2F%20A%20possible%20representation%20of%20a%20Maybe%0D%0Aconst%20k%20%3D%20Symbol(%22my%20maybe%20key%22)%3B%0D%0Atype%20Maybe%3CT%3E%20%3D%20%7B%20%5Bk%5D%3A%20T%20%7C%20undefined%20%7D%3B%0D%0A%0D%0Ainterface%20TypeProps%3CType%2C%20Params%20extends%20Tuple%20%3D%20never%3E%20%7B%0D%0A%20%20%5Bk%5D%3A%20%7B%0D%0A%20%20%20%20parameters%3A%20Type%20extends%20Maybe%3Cinfer%20A%3E%20%3F%20%5BA%5D%20%3A%20never%3B%0D%0A%20%20%20%20type%3A%20Type%20extends%20Maybe%3Cany%3E%20%3F%20Maybe%3CParams%5B0%5D%3E%20%3A%20never%3B%0D%0A%20%20%7D%3B%0D%0A%7D%0D%0A%0D%0Aconst%20Just%20%3D%20%3CT%3E(x%3A%20T)%20%3D%3E%20(%7B%20%5Bk%5D%3A%20x%20%7D%20as%20Maybe%3CT%3E)%3B%0D%0Aconst%20None%20%3D%20%7B%7D%20as%20Maybe%3Cundefined%3E%3B%0D%0A%0D%0Aconst%20match%3A%20%3CT%2C%20U%3E(%0D%0A%20%20%7B%0D%0A%20%20%20%20Map%2C%0D%0A%20%20%20%20None%0D%0A%20%20%7D%3A%20%7B%0D%0A%20%20%20%20%20%20Map%3A%20(x%3A%20T)%20%3D%3E%20Maybe%3CU%3E%3B%0D%0A%20%20%20%20%20%20None%3A%20Maybe%3Cundefined%3E%3B%0D%0A%20%20%20%20%7D%0D%0A)%20%3D%3E%20(o%3A%20Maybe%3CT%3E)%20%3D%3E%20Maybe%3CU%3E%20%3D%20%3CT%2C%20U%3E(%7B%0D%0A%20%20Map%2C%0D%0A%20%20None%0D%0A%7D%3A%20%7B%0D%0A%20%20%20%20Map%3A%20(x%3A%20T)%20%3D%3E%20Maybe%3CU%3E%3B%0D%0A%20%20%20%20None%3A%20Maybe%3Cundefined%3E%3B%0D%0A%20%20%7D)%20%3D%3E%20(o%3A%20Maybe%3CT%3E)%20%3D%3E%20(o.hasOwnProperty(k)%20%3F%20Map(o%5Bk%5D!)%20%3A%20None)%20as%20Maybe%3CU%3E%3B%0D%0A%0D%0Aconst%20%7B%20map%2C%20chain%2C%20of%20%7D%20%3D%20GenericMaybe(%7B%20Just%2C%20None%2C%20match%20%7D)%3B%0D%0A%0D%0A%2F%2F%20Examples%0D%0Aconsole.log(%5B%0D%0A%20%20map((x%3A%20number)%20%3D%3E%20x%20%2B%202)(of(42))%2C%0D%0A%20%20map((x%3A%20number)%20%3D%3E%20x%20%2B%202)(None)%2C%0D%0A%20%20chain((x%3A%20number)%20%3D%3E%20(x%20%3E%2040%20%3F%20None%20%3A%20of(x%20%202))%20as%20Maybe%3Cnumber%3E)(of(42))%2C%0D%0A%20%20chain((x%3A%20number)%20%3D%3E%20(x%20%3E%2040%20%3F%20None%20%3A%20of(x%20%202))%20as%20Maybe%3Cnumber%3E)(of(32))%2C%0D%0A%20%20map((x%3A%20number)%20%3D%3E%20None)(of(42))%2C%0D%0A%20%20map((x%3A%20number)%20%3D%3E%20of(x%20*%202))(of(42))%0D%0A%5D)%3B)

KiaraGrouwstra commented 6 years ago

@SimonMeskens: Looks pretty interesting! Have you considered reposting to https://github.com/Microsoft/TypeScript/issues/1213 and maybe trying a PR to fp-ts? :)

SimonMeskens commented 6 years ago

I'm creating a new npm module that allows you to write this code and I'll ask if fp-ts is interested in using it. It would be a massive breaking change for them, so maybe down the line. The advantages my system has (once the bugs are out) over fp-ts is that it doesn't need to decorate HKTs with extra ghost properties. Also, it does proper type inference, so the second the compiler figures out which HKT we're talking about, it'll give it to you. One big issue I'm having is that I'm getting way worse intellisense. While you're writing code before the compiler figures out the HKT, the type hover can show like 70 lines of typing code.

If you want to follow along with the current progress, the repo is here: https://github.com/SimonMeskens/TypeProps/issues/1

I'll try to remember to also post my findings to the upstream TypeScript issue.

KiaraGrouwstra commented 6 years ago

To me it's looking good, so hope this gets noticed by some others with more HKT experience. Time to link this from the HKT thread. :)

SimonMeskens commented 6 years ago

There are a few bugs, but I was provided with some perfectly abstract code samples, so I'm putting it through its paces with some real code. So far, the library itself has held up perfectly, except for one missing feature I'm now working on. After that, I'll upload an alpha version and link it. Then afterwards, I'll start adding some features, it's going to stay very lightweight, but I want to make it ready to support fantasy-land and I have some ideas for that. As for progress, I tested the Monad interface and it works perfectly so far, still have to test inference, but should also be fine.

KiaraGrouwstra commented 6 years ago

That's great, thanks! @gcanti, what's your take on the innovations and potential pitfalls here?

SimonMeskens commented 6 years ago

From my perspective, these are the innovations:

As for cons:

In other words, there's pros/cons.

SimonMeskens commented 6 years ago

Huh, interesting thought, I think I accidentally wrote a pattern matching type actually. The only issue is that I can't make it a full-blown pattern matcher due to Microsoft/TypeScript#22617. It will work for HKTs, but I can't generalize it to a pattern matcher.

    type TypeMatch<
        T,
        Match extends <T>() => {},
        TProps = ReturnType<Match>
    > = TProps[keyof TProps];

    // Test is never due to #22617
    type Test = TypeMatch<number, <T>() => {
        number: T extends number ? number : never;
    }>

The reason this is better than writing a manual pattern match using conditional types is that it's composable. I'm using that composability to allow users to store a bunch of type matchers in a global type and then use those to resolve HKTs. The value for HKTs is then in my tuple manipulation of the type parameters.

Unfortunately, that issue has been flagged as Design Limitation, so it'll be hard to get traction. I ran into this same issue several times already trying to write the library.

SimonMeskens commented 6 years ago

Example wasn't correct, this is what I meant:

type TypeMatch<
        T,
        Match extends <U>(a: U) => {}
    > = Match extends (a: T) => infer U ? U : never;

    // Test is never due to #22617
    type Test = TypeMatch<Array<number>, <T>(a: T) => {
        number: T extends Array<infer U> ? Array<U> : never;
    }>

I think there would be tremendous value in this, maybe I should finally learn the TypeScript codebase and propose a PR.

KiaraGrouwstra commented 6 years ago

composable

yeah I'd done something similar over here :), I see where you're coming from with that.

in my limited HKT typing experience, the pros/cons are looking pretty fair. subscribing to your repo, can't wait to see what'll come out of it!

SimonMeskens commented 6 years ago

The current set of files in the repo under /examples showcase what's possible at the limit. So far, from testing, concrete monads should be fairly straightforward and simple, the example of generic monads based on pattern matched ADTs is about as complex as you can get and really fiddly, but once typed, it works. I'm very happy with how it's performing so far and I plan on releasing it once TS 2.9 hits (I need the new keyof mechanics, so I'm currently using a nightly). There are still some warts overall, but this library should be about as complex as we can get without some form of infer + generic functions.

If only we had something like:

type Test2<T, R> = T extends <U = R>() => infer V ? V : never;

Note how I'm passing the type R to the generic infer. If that very simple change would make it into the language, we could do so much more, but as it is, infer isn't that useful for higher abstractions.

KiaraGrouwstra commented 6 years ago

That one does look pretty tough...

/cc @gigobyte: maybe TypeProps would help type pure? :)

SimonMeskens commented 6 years ago

Yeah, that solution above is probably pretty nonsensical actually.

What I need is a way to do this:

type Lambda = <U>() => U[]
type ReturnTypeWithGeneric<T, P> = ...
type Test = ReturnTypeWithGeneric<Lambda, string>

And have Test be of type string[]. I don't think conditionals can do it by design unfortunately. I think we'd need something like type level function apply?

KiaraGrouwstra commented 6 years ago

Right. It seems tough though, as you might need to be able to guarantee generic arities match up, if that makes sense. Not saying it can't be done, but yeah, so far I don't think it has yet.

SimonMeskens commented 6 years ago

That's why I was looking at a solution with conditionals, because conditionals already put the burden of matching on the programmer. If the arity doesn't match, return the false path, but I don't think conditionals are supposed to work like that

KiaraGrouwstra commented 6 years ago

sounds like 6606 to me, but I know I tend to say that a lot. I mean, (v: U) => U[] would make sense, and we could check arity there too. Then again, this also implies type-level applyication with spread (#18007).

SimonMeskens commented 6 years ago

For those following along, I think this example (also posted to the TS github) more or less shows the power of my latest experiments:

type unknown = {} | null | undefined;

// Functor
interface StaticFunctor<G> {
    map<F extends Generic<G>, U>(
        transform: (a: Parameters<F>[0]) => U,
        mappable: F
    ): Generic<F, [U]>;
}

// Examples
const arrayFunctor: StaticFunctor<any[]> = {
    map: <A, B>(fn: (a: A) => B, fa: A[]): B[] => {
        return fa.map(fn);
    }
};
const objectFunctor: StaticFunctor<object> = {
    map: <A, B>(fn: (a: A) => B, fa: A): B => {
        return fn(fa);
    }
};
const nullableFunctor: StaticFunctor<object | null | undefined> = {
    map: <A, B>(
        fn: (a: A) => B,
        fa: A | null | undefined
    ): B | null | undefined => {
        return fa != undefined ? fn(fa) : fa;
    }
};

const doubler = (x: number) => x * 2;

const xs = arrayFunctor.map(doubler, [4, 2]); // xs: number[]
const x = objectFunctor.map(doubler, 42); // x: number
const xNull = nullableFunctor.map(doubler, null); // xNull: null
const xSome = nullableFunctor.map(doubler, 4 as number | undefined); // xSome: number | undefined

const functor: StaticFunctor<unknown | any[]> = {
    map(fn, fa) {
        return Array.isArray(fa)
            ? arrayFunctor.map(fn, fa)
            : fa != undefined
                ? objectFunctor.map(fn, fa)
                : nullableFunctor.map(fn, fa);
    }
};

const ys = functor.map(doubler, [4, 2]); // ys: number[]
const y = functor.map(doubler, 42); // y: number
const yNull = functor.map(doubler, null); // yNull: null
const ySome = functor.map(doubler, 42 as number | undefined); // ySome: number | undefined

// Plumbing
interface TypeProps<T = {}, Params extends ArrayLike<any> = never> {
    array: {
        infer: T extends Array<infer A> ? [A] : never;
        construct: Params[0][];
    };
    null: {
        infer: null extends T ? [never] : never;
        construct: null;
    };
    undefined: {
        infer: undefined extends T ? [never] : never;
        construct: undefined;
    };
    unfound: {
        infer: [NonNullable<T>];
        construct: Params[0];
    };
}

type Match<T> = T extends infer U
    ? ({} extends U ? any
        : TypeProps<U>[Exclude<keyof TypeProps, "unfound">]["infer"]) extends never
    ? "unfound"
    : {
        [Key in Exclude<keyof TypeProps, "unfound">]:
        TypeProps<T>[Key]["infer"] extends never
        ? never : Key
    }[Exclude<keyof TypeProps, "unfound">] : never;

type Parameters<T> = TypeProps<T>[Match<T>]["infer"];

type Generic<
    T,
    Params extends ArrayLike<any> = ArrayLike<any>,
    > = TypeProps<T, Params>[Match<T>]["construct"];

This one doesn't have the mapping stuff yet of TypeProps proper, but it has some new tricks up its sleeve. For mapping, I'm looking at finding a way to get closer to Haskell, where you can define an instance type like Maybe (Either e)

SimonMeskens commented 6 years ago

TypeProps just reached stable alpha, I just typed some really complex examples, including Haskell-style instance types. I'm going to close this issue down.

Next step is publishing on NPM and making a new repo to provide Fantasy-land, Static-land and some other varieties

Thanks for the help Tycho :)