New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow classes to be parametric in other parametric classes #1213

Open
metaweta opened this Issue Nov 19, 2014 · 115 comments

Comments

Projects
None yet
@metaweta

metaweta commented Nov 19, 2014

This is a proposal for allowing generics as type parameters. It's currently possible to write specific examples of monads, but in order to write the interface that all monads satisfy, I propose writing

interface Monad<T<~>> {
  map<A, B>(f: (a: A) => B): T<A> => T<B>;
  lift<A>(a: A): T<A>;
  join<A>(tta: T<T<A>>): T<A>;
}

Similarly, it's possible to write specific examples of cartesian functors, but in order to write the interface that all cartesian functors satisfy, I propose writing

interface Cartesian<T<~>> {
  all<A>(a: Array<T<A>>): T<Array<A>>;
}

Parametric type parameters can take any number of arguments:

interface Foo<T<~,~>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

That is, when a type parameter is followed by a tilde and a natural arity, the type parameter should be allowed to be used as a generic type with the given arity in the rest of the declaration.

Just as is the case now, when implementing such an interface, the generic type parameters should be filled in:

class ArrayMonad<A> implements Monad<Array> {
  map<A, B>(f: (a:A) => B): Array<A> => Array<B> {
    return (arr: Array<A>) =>  arr.map(f);
  }
  lift<A>(a: A): Array<A> { return [a]; }
  join<A>(tta: Array<Array<A>>): Array<A> {
    return tta.reduce((prev, cur) => prev.concat(cur));
  }
}

In addition to directly allowing compositions of generic types in the arguments, I propose that typedefs also support defining generics in this way (see issue 308):

typedef Maybe<Array<~>> Composite<~> ;
class Foo implements Monad<Composite<~>> { ... }

The arities of the definition and the alias must match for the typedef to be valid.

@DanielRosenwasser

This comment has been minimized.

Show comment
Hide comment
@DanielRosenwasser

DanielRosenwasser Nov 19, 2014

Member

Not to make any rash assumptions, but I believe you're typing it incorrectly. All parameter types require parameter names, so you probably meant to type

map<A, B>(f: (x: A) => B): T<A> => T<B>;

whereas right now map is a function that takes a mapper from type any (where your parameter name is A) to B.

Try using the --noImplicitAny flag for better results.

Member

DanielRosenwasser commented Nov 19, 2014

Not to make any rash assumptions, but I believe you're typing it incorrectly. All parameter types require parameter names, so you probably meant to type

map<A, B>(f: (x: A) => B): T<A> => T<B>;

whereas right now map is a function that takes a mapper from type any (where your parameter name is A) to B.

Try using the --noImplicitAny flag for better results.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Nov 19, 2014

Thanks, corrected.

metaweta commented Nov 19, 2014

Thanks, corrected.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Nov 28, 2014

I've updated my comment into a proposal.

metaweta commented Nov 28, 2014

I've updated my comment into a proposal.

@fdecampredon

This comment has been minimized.

Show comment
Hide comment
@fdecampredon

fdecampredon Jan 27, 2015

👍 higher kinded type would be a big bonus for functional programming construct, however before that I would prefer to have correct support for higher order function and generic :p

fdecampredon commented Jan 27, 2015

👍 higher kinded type would be a big bonus for functional programming construct, however before that I would prefer to have correct support for higher order function and generic :p

@RyanCavanaugh RyanCavanaugh added this to the Community milestone Apr 28, 2015

@RyanCavanaugh

This comment has been minimized.

Show comment
Hide comment
@RyanCavanaugh

RyanCavanaugh Apr 28, 2015

Member

Quasi-approved.

We like this idea a lot, but need a working implementation to try out to understand all the implications and potential edge cases. Having a sample PR that at least tackles the 80% use cases of this would be a really helpful next step.

Member

RyanCavanaugh commented Apr 28, 2015

Quasi-approved.

We like this idea a lot, but need a working implementation to try out to understand all the implications and potential edge cases. Having a sample PR that at least tackles the 80% use cases of this would be a really helpful next step.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Apr 28, 2015

What are people's opinions on the tilde syntax? An alternative to T~2 would be something like

interface Foo<T<~,~>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

that allows direct composition of generics instead of needing type aliases:

interface Foo<T<~,~,~>, U<~>, V<~, ~>> {
  bar<A, B, C, D>(a: A, f: (b: B) => C, d: D): T<U<A>, V<B, C>, D>;
}

metaweta commented Apr 28, 2015

What are people's opinions on the tilde syntax? An alternative to T~2 would be something like

interface Foo<T<~,~>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

that allows direct composition of generics instead of needing type aliases:

interface Foo<T<~,~,~>, U<~>, V<~, ~>> {
  bar<A, B, C, D>(a: A, f: (b: B) => C, d: D): T<U<A>, V<B, C>, D>;
}
@DanielRosenwasser

This comment has been minimized.

Show comment
Hide comment
@DanielRosenwasser

DanielRosenwasser Apr 28, 2015

Member

It's odd to have explicit arity since we don't really do that anywhere else, so

interface Foo<T<~,~>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

is a little clearer, though, I know other languages use * in similar contexts instead of ~:

interface Foo<T<*,*>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

Though taking that point to an extreme, you might get:

interface Foo<T: (*,*) => *> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}
Member

DanielRosenwasser commented Apr 28, 2015

It's odd to have explicit arity since we don't really do that anywhere else, so

interface Foo<T<~,~>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

is a little clearer, though, I know other languages use * in similar contexts instead of ~:

interface Foo<T<*,*>> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}

Though taking that point to an extreme, you might get:

interface Foo<T: (*,*) => *> {
  bar<A, B>(f: (a: A) => B): T<A, B>;
}
@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Apr 28, 2015

I think T<~,~> is clearer than T~2, too. I'll modify the proposal above. I don't care whether we use ~ or *; it just can't be a JS identifier, so we can't use, say, _ . I don't see what benefit the => notation provides; all generics take some input types and return a single output type.

metaweta commented Apr 28, 2015

I think T<~,~> is clearer than T~2, too. I'll modify the proposal above. I don't care whether we use ~ or *; it just can't be a JS identifier, so we can't use, say, _ . I don't see what benefit the => notation provides; all generics take some input types and return a single output type.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Apr 28, 2015

A lighter-weight syntax would be leaving off the arity of the generics entirely; the parser would figure it out from the first use and throw an error if the rest weren't consistent with it.

metaweta commented Apr 28, 2015

A lighter-weight syntax would be leaving off the arity of the generics entirely; the parser would figure it out from the first use and throw an error if the rest weren't consistent with it.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Jun 1, 2015

I'd be happy to start work on implementing this feature. What's the recommended forum for pestering devs about transpiler implementation details?

metaweta commented Jun 1, 2015

I'd be happy to start work on implementing this feature. What's the recommended forum for pestering devs about transpiler implementation details?

@danquirk

This comment has been minimized.

Show comment
Hide comment
@danquirk

danquirk Jun 1, 2015

Member

You can log many new issues for larger questions with more involved code samples, or make a long running issue with a series of questions as you go. Alternatively you can join the chat room here https://gitter.im/Microsoft/TypeScript and we can talk there.

Member

danquirk commented Jun 1, 2015

You can log many new issues for larger questions with more involved code samples, or make a long running issue with a series of questions as you go. Alternatively you can join the chat room here https://gitter.im/Microsoft/TypeScript and we can talk there.

@Artazor

This comment has been minimized.

Show comment
Hide comment
@Artazor

Artazor Dec 10, 2015

Contributor

@metaweta any news? If you need any help/discussion I would be glad to brainstorm on this issue. I really want this feature.

Contributor

Artazor commented Dec 10, 2015

@metaweta any news? If you need any help/discussion I would be glad to brainstorm on this issue. I really want this feature.

@metaweta

This comment has been minimized.

Show comment
Hide comment
@metaweta

metaweta Dec 10, 2015

No, things at work took over what free time I had to work on it.

metaweta commented Dec 10, 2015

No, things at work took over what free time I had to work on it.

@aleksey-bykov

This comment has been minimized.

Show comment
Hide comment
@aleksey-bykov

aleksey-bykov Feb 29, 2016

bump: is there a chance to see this feature ever considered?

aleksey-bykov commented Feb 29, 2016

bump: is there a chance to see this feature ever considered?

@RyanCavanaugh

This comment has been minimized.

Show comment
Hide comment
@RyanCavanaugh

RyanCavanaugh Feb 29, 2016

Member

#1213 (comment) is still the current state of it. I don't see anything here that would make us change the priority of the feature.

Member

RyanCavanaugh commented Feb 29, 2016

#1213 (comment) is still the current state of it. I don't see anything here that would make us change the priority of the feature.

@spion

This comment has been minimized.

Show comment
Hide comment
@spion

spion Apr 18, 2016

Seems to me like this is useful in far more situations than just importing category theory abstractions. For example, it would be useful to be able to write module factories that take a Promise implementation (constructor) as an argument, e.g. a Database with a pluggable promise implementation:

interface Database<P<~> extends PromiseLike<~>> {   
    query<T>(s:string, args:any[]): P<T> 
}

spion commented Apr 18, 2016

Seems to me like this is useful in far more situations than just importing category theory abstractions. For example, it would be useful to be able to write module factories that take a Promise implementation (constructor) as an argument, e.g. a Database with a pluggable promise implementation:

interface Database<P<~> extends PromiseLike<~>> {   
    query<T>(s:string, args:any[]): P<T> 
}
@jack-williams

This comment has been minimized.

Show comment
Hide comment
@jack-williams

jack-williams Mar 29, 2018

Contributor

@tycho01 Would all these problems go away if people explicitly instantiated T?

I think that is reasonable, given that I doubt inference can be solved for all cases anyway.

Contributor

jack-williams commented Mar 29, 2018

@tycho01 Would all these problems go away if people explicitly instantiated T?

I think that is reasonable, given that I doubt inference can be solved for all cases anyway.

@tycho01

This comment has been minimized.

Show comment
Hide comment
@tycho01

tycho01 Mar 29, 2018

Contributor

@jack-williams: not with #17961 so far, but I think using it for dispatching might help:

let arr = [1, 2, 3];
let inc = (n: number) => n + 1;
let c = arr.map(inc); // number[]
let map = <Functor extends { map: Function }, Fn extends Function>(x: Functor, f: Fn) => x['map'](f); // any on 2.7 :(
let e = map(arr, inc);
Contributor

tycho01 commented Mar 29, 2018

@jack-williams: not with #17961 so far, but I think using it for dispatching might help:

let arr = [1, 2, 3];
let inc = (n: number) => n + 1;
let c = arr.map(inc); // number[]
let map = <Functor extends { map: Function }, Fn extends Function>(x: Functor, f: Fn) => x['map'](f); // any on 2.7 :(
let e = map(arr, inc);
@jack-williams

This comment has been minimized.

Show comment
Hide comment
@jack-williams

jack-williams Apr 1, 2018

Contributor

@tycho01 Yes I realised my suggestion was terrible because T isn't instantiated at the method calls.

Would something like the following work?

interface TyCon<A> {
    C: <A>(x: A) => TyCon<A>
}

interface Functor<A> extends TyCon<A> {
    C: <A>(x: A) => Functor<A>;
    fmap<B>(this: this["C"](A), f: (x: A) => B): this["C"](B);
}

interface Option<A> extends Functor<A> {
    C: <A>(x: A) => Option<A>;
}
Contributor

jack-williams commented Apr 1, 2018

@tycho01 Yes I realised my suggestion was terrible because T isn't instantiated at the method calls.

Would something like the following work?

interface TyCon<A> {
    C: <A>(x: A) => TyCon<A>
}

interface Functor<A> extends TyCon<A> {
    C: <A>(x: A) => Functor<A>;
    fmap<B>(this: this["C"](A), f: (x: A) => B): this["C"](B);
}

interface Option<A> extends Functor<A> {
    C: <A>(x: A) => Option<A>;
}
@tycho01

This comment has been minimized.

Show comment
Hide comment
@tycho01

tycho01 Apr 2, 2018

Contributor

@jack-williams I guess the question should be how it would compare in behavior to the ADT implementation in fp-ts, but this looks like it could work, yeah. Probably also without the TyCon.

Contributor

tycho01 commented Apr 2, 2018

@jack-williams I guess the question should be how it would compare in behavior to the ADT implementation in fp-ts, but this looks like it could work, yeah. Probably also without the TyCon.

@tycho01

This comment has been minimized.

Show comment
Hide comment
@tycho01

tycho01 Apr 2, 2018

Contributor

@jack-williams @isiahmeadows:

I tried the idea at try flow, since it already has $Call available. For me it seems to become unresponsive somehow though...

interface Functor<A> {
    C: <A>(x: A) => Functor<A>;
    fmap<B>(f: (x: A) => B): $Call<$ElementType<this, "C">, B>;
}
// this: $Call<$ElementType<this, "C">, A>, 
// ^ flow doesn't seem to do `this` params

interface Option<A> extends Functor<A> {
    C: <A>(x: A) => Option<A>;
}

let o: Option<string>;
let f: (s: string) => number;
let b = o.fmap(f);
Contributor

tycho01 commented Apr 2, 2018

@jack-williams @isiahmeadows:

I tried the idea at try flow, since it already has $Call available. For me it seems to become unresponsive somehow though...

interface Functor<A> {
    C: <A>(x: A) => Functor<A>;
    fmap<B>(f: (x: A) => B): $Call<$ElementType<this, "C">, B>;
}
// this: $Call<$ElementType<this, "C">, A>, 
// ^ flow doesn't seem to do `this` params

interface Option<A> extends Functor<A> {
    C: <A>(x: A) => Option<A>;
}

let o: Option<string>;
let f: (s: string) => number;
let b = o.fmap(f);
@goodmind

This comment has been minimized.

Show comment
Hide comment
@goodmind

goodmind Apr 3, 2018

@tycho01 I think you can't just get properties with $ElementType from this in flow

goodmind commented Apr 3, 2018

@tycho01 I think you can't just get properties with $ElementType from this in flow

@goodmind

This comment has been minimized.

Show comment
Hide comment
@goodmind

goodmind Apr 3, 2018

@tycho01 you actually can't get this to work in typescript too
playground: https://goo.gl/tMBKyJ

goodmind commented Apr 3, 2018

@tycho01 you actually can't get this to work in typescript too
playground: https://goo.gl/tMBKyJ

@tycho01

This comment has been minimized.

Show comment
Hide comment
@tycho01

tycho01 Apr 7, 2018

Contributor

@goodmind: hm, looks like it infers Maybe<number> instead of Functor<number> after copying over fmap from Functor to Maybe.
With type calls I guess that would improve to having just the type there rather than needing the run-time implementation for the type.
Now, functors would need their own fmap implementations already. That would suck for the derived methods though.
Back to square one. :/

Contributor

tycho01 commented Apr 7, 2018

@goodmind: hm, looks like it infers Maybe<number> instead of Functor<number> after copying over fmap from Functor to Maybe.
With type calls I guess that would improve to having just the type there rather than needing the run-time implementation for the type.
Now, functors would need their own fmap implementations already. That would suck for the derived methods though.
Back to square one. :/

@tycho01

This comment has been minimized.

Show comment
Hide comment
@tycho01

tycho01 Apr 22, 2018

Contributor

Some relevant ideas over at SimonMeskens/TypeProps#1.

Contributor

tycho01 commented Apr 22, 2018

Some relevant ideas over at SimonMeskens/TypeProps#1.

@SimonMeskens

This comment has been minimized.

Show comment
Hide comment
@SimonMeskens

SimonMeskens Apr 23, 2018

I'm planning to release an alpha version ASAP, but you can follow along with me writing the examples in that issue to already get a feel for it.

This particular issue is a bit long to go through entirely, but what I'm looking for is simple contained, but real examples of code that you aren't able to type because of lack of parameterized generic types. I think I can type most of them (provided they don't rely on abstract lifted type constructors). Feel free to open issues in the above repo with code and I'll type them for you if I can (or you can post them here too).

SimonMeskens commented Apr 23, 2018

I'm planning to release an alpha version ASAP, but you can follow along with me writing the examples in that issue to already get a feel for it.

This particular issue is a bit long to go through entirely, but what I'm looking for is simple contained, but real examples of code that you aren't able to type because of lack of parameterized generic types. I think I can type most of them (provided they don't rely on abstract lifted type constructors). Feel free to open issues in the above repo with code and I'll type them for you if I can (or you can post them here too).

@kpdonn

This comment has been minimized.

Show comment
Hide comment
@kpdonn

kpdonn May 1, 2018

Contributor

Heads up I've started an attempt at implementing this at #23809. It's still very incomplete but check it out if you are interested.

Contributor

kpdonn commented May 1, 2018

Heads up I've started an attempt at implementing this at #23809. It's still very incomplete but check it out if you are interested.

@SimonMeskens

This comment has been minimized.

Show comment
Hide comment
@SimonMeskens

SimonMeskens May 2, 2018

I promised you guys a simple example, here it is. This uses a few tricks I learned from writing my library.

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 May 2, 2018

I promised you guys a simple example, here it is. This uses a few tricks I learned from writing my library.

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

This comment has been minimized.

Show comment
Hide comment
@SimonMeskens

SimonMeskens May 4, 2018

I updated and simplified the sample, here's a playground link too:
Playground

SimonMeskens commented May 4, 2018

I updated and simplified the sample, here's a playground link too:
Playground

@SimonMeskens

This comment has been minimized.

Show comment
Hide comment
@SimonMeskens

SimonMeskens May 5, 2018

I added an NPM library for the above, so you can work with it easier. Currently in alpha until I get proper testing in, but should help you guys trying to write HKTs.

Github Link

SimonMeskens commented May 5, 2018

I added an NPM library for the above, so you can work with it easier. Currently in alpha until I get proper testing in, but should help you guys trying to write HKTs.

Github Link

@pelotom

This comment has been minimized.

Show comment
Hide comment
@pelotom

pelotom Aug 24, 2018

I've been playing with a simple approach to simulating HKTs by using conditional types to substitute virtual type variables within a saturated type:

declare const index: unique symbol;

// A type for representing type variables
type _<N extends number = 0> = { [index]: N };

// Type application (substitutes type variables with types)
type $<T, S, N extends number = 0> =
  T extends _<N> ? S :
  T extends undefined | null | boolean | string | number ? T :
  T extends Array<infer A> ? $Array<A, S, N> :
  T extends (x: infer I) => infer O ? (x: $<I, S, N>) => $<O, S, N> :
  T extends object ? { [K in keyof T]: $<T[K], S, N> } :
  T;

interface $Array<T, S, N extends number> extends Array<$<T, S, N>> {}

// Let's declare some familiar type classes...

interface Functor<F> {
  map: <A, B>(fa: $<F, A>, f: (a: A) => B) => $<F, B>;
}

interface Monad<M> {
  pure: <A>(a: A) => $<M, A>;
  bind: <A, B>(ma: $<M, A>, f: (a: A) => $<M, B>) => $<M, B>;
}

interface MonadLib<M> extends Monad<M>, Functor<M> {
  join: <A>(mma: $<M, $<M, A>>) => $<M, A>;
  // sequence, etc...
}

const Monad = <M>({ pure, bind }: Monad<M>): MonadLib<M> => ({
  pure,
  bind,
  map: (ma, f) => bind(ma, a => pure(f(a))),
  join: mma => bind(mma, ma => ma),
});

// ... and an instance

type Maybe<A> = { tag: 'none' } | { tag: 'some'; value: A };
const none: Maybe<never> = { tag: 'none' };
const some = <A>(value: A): Maybe<A> => ({ tag: 'some', value });

const { map, join } = Monad<Maybe<_>>({
  pure: some,
  bind: (ma, f) => ma.tag === 'some' ? f(ma.value) : ma,
});

// Not sure why the `<number>` annotation is required here...
const result = map(join<number>(some(some(42))), n => n + 1);
expect(result).toEqual(some(43));

Project here: https://github.com/pelotom/hkts

Feedback welcome!

pelotom commented Aug 24, 2018

I've been playing with a simple approach to simulating HKTs by using conditional types to substitute virtual type variables within a saturated type:

declare const index: unique symbol;

// A type for representing type variables
type _<N extends number = 0> = { [index]: N };

// Type application (substitutes type variables with types)
type $<T, S, N extends number = 0> =
  T extends _<N> ? S :
  T extends undefined | null | boolean | string | number ? T :
  T extends Array<infer A> ? $Array<A, S, N> :
  T extends (x: infer I) => infer O ? (x: $<I, S, N>) => $<O, S, N> :
  T extends object ? { [K in keyof T]: $<T[K], S, N> } :
  T;

interface $Array<T, S, N extends number> extends Array<$<T, S, N>> {}

// Let's declare some familiar type classes...

interface Functor<F> {
  map: <A, B>(fa: $<F, A>, f: (a: A) => B) => $<F, B>;
}

interface Monad<M> {
  pure: <A>(a: A) => $<M, A>;
  bind: <A, B>(ma: $<M, A>, f: (a: A) => $<M, B>) => $<M, B>;
}

interface MonadLib<M> extends Monad<M>, Functor<M> {
  join: <A>(mma: $<M, $<M, A>>) => $<M, A>;
  // sequence, etc...
}

const Monad = <M>({ pure, bind }: Monad<M>): MonadLib<M> => ({
  pure,
  bind,
  map: (ma, f) => bind(ma, a => pure(f(a))),
  join: mma => bind(mma, ma => ma),
});

// ... and an instance

type Maybe<A> = { tag: 'none' } | { tag: 'some'; value: A };
const none: Maybe<never> = { tag: 'none' };
const some = <A>(value: A): Maybe<A> => ({ tag: 'some', value });

const { map, join } = Monad<Maybe<_>>({
  pure: some,
  bind: (ma, f) => ma.tag === 'some' ? f(ma.value) : ma,
});

// Not sure why the `<number>` annotation is required here...
const result = map(join<number>(some(some(42))), n => n + 1);
expect(result).toEqual(some(43));

Project here: https://github.com/pelotom/hkts

Feedback welcome!

@mlhaufe

This comment has been minimized.

Show comment
Hide comment
@mlhaufe

mlhaufe Aug 25, 2018

@pelotom I like the lightness of the syntax of your approach. There are two other approaches that haven't been mentioned in this thread yet that might stir some creativity in how current and future solutions are produced. Both are Object-Oriented solutions to this problem.

  1. Bertrand Meyer described a way to simulate generic types in his 1988 book "Object-oriented Software Construction" .

The examples are in Eiffel, but a rough translation to TypeScript looks like this:

https://gist.github.com/mlhaufe/089004abd14ad8e7171e2a122198637f

You'll notice they can get pretty heavy due to the need for intermediate class representations, but with a form of class-factory or with the TypeScript Mixin approach this could be reduced significantly.

There may be some applicability to #17588

  1. The second approach is used when simulating Object Algebras (and Abstract Factories):

C<T> is represented by App<t,T> where T is the class, and t is a unique tag associated with C

interface App<C,T> {}

Sample:

interface IApp<C,T> {}

interface IList<C> {
    Nil<T>(): IApp<C,T>
    Cons<T>(head: T, tail: IList<C>): IApp<C,T>
}

// defining data
abstract class List<T> implements IApp<typeof List, T> {
    // type-safe down-cast
    static prj<U>(app: IApp<typeof List, U>): List<U> { return app as List<U> }
}
class Nil<T> extends List<T> { }
class Cons<T> extends List<T> {
    constructor(readonly head: T, readonly tail: List<T>) {
        super()
    }
}

// The abstract factory where the HKT is needed
class ListFactory<T> implements IList<typeof List> {
    Nil<T>(): IApp<typeof List, T> { return new Nil() }
    Cons<T>(head: T, tail: IApp<typeof List, T>): IApp<typeof List, T> {
        return new Cons(head, tail)
    }
}

You can see more details and justification in the following paper under section 3.5 "Emulating Type-Constructor Polymorphism":

https://blog.acolyer.org/2015/08/13/streams-a-la-carte-extensible-pipelines-with-object-algebras/

mlhaufe commented Aug 25, 2018

@pelotom I like the lightness of the syntax of your approach. There are two other approaches that haven't been mentioned in this thread yet that might stir some creativity in how current and future solutions are produced. Both are Object-Oriented solutions to this problem.

  1. Bertrand Meyer described a way to simulate generic types in his 1988 book "Object-oriented Software Construction" .

The examples are in Eiffel, but a rough translation to TypeScript looks like this:

https://gist.github.com/mlhaufe/089004abd14ad8e7171e2a122198637f

You'll notice they can get pretty heavy due to the need for intermediate class representations, but with a form of class-factory or with the TypeScript Mixin approach this could be reduced significantly.

There may be some applicability to #17588

  1. The second approach is used when simulating Object Algebras (and Abstract Factories):

C<T> is represented by App<t,T> where T is the class, and t is a unique tag associated with C

interface App<C,T> {}

Sample:

interface IApp<C,T> {}

interface IList<C> {
    Nil<T>(): IApp<C,T>
    Cons<T>(head: T, tail: IList<C>): IApp<C,T>
}

// defining data
abstract class List<T> implements IApp<typeof List, T> {
    // type-safe down-cast
    static prj<U>(app: IApp<typeof List, U>): List<U> { return app as List<U> }
}
class Nil<T> extends List<T> { }
class Cons<T> extends List<T> {
    constructor(readonly head: T, readonly tail: List<T>) {
        super()
    }
}

// The abstract factory where the HKT is needed
class ListFactory<T> implements IList<typeof List> {
    Nil<T>(): IApp<typeof List, T> { return new Nil() }
    Cons<T>(head: T, tail: IApp<typeof List, T>): IApp<typeof List, T> {
        return new Cons(head, tail)
    }
}

You can see more details and justification in the following paper under section 3.5 "Emulating Type-Constructor Polymorphism":

https://blog.acolyer.org/2015/08/13/streams-a-la-carte-extensible-pipelines-with-object-algebras/

@aleksey-bykov

This comment has been minimized.

Show comment
Hide comment
@aleksey-bykov

aleksey-bykov Oct 8, 2018

@metaweta, can you rename this issue to Higher kinded types in TypeScript so it gets a better visibility from google search please?

aleksey-bykov commented Oct 8, 2018

@metaweta, can you rename this issue to Higher kinded types in TypeScript so it gets a better visibility from google search please?

@jcalz

This comment has been minimized.

Show comment
Hide comment
@jcalz

jcalz Oct 22, 2018

Contributor

Perhaps our wise and benevolent repository maintainers (e.g., @RyanCavanaugh, @DanielRosenwasser ) could edit the title, if such a change be deemed worthy of their intervention?

Contributor

jcalz commented Oct 22, 2018

Perhaps our wise and benevolent repository maintainers (e.g., @RyanCavanaugh, @DanielRosenwasser ) could edit the title, if such a change be deemed worthy of their intervention?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment