Better encoding for HKTs

[ENvironmentSet]

🚀 Feature request

Current Behavior

Currently, we're using declaration merging and type level defunctionalization to simulate HKTs. They did their job well, but there was fundamental problem.

They're too verbose to use!

When we define some data type that's constructor is HKT, we need to define URI for it and extend proper URItoKind interface by declaration merging. this is not only boring work but also producing unreadable code.

https://github.com/gcanti/fp-ts/blob/e708323cfcff0b4e013ecf6f90a00816fb943a64/src/Option.ts#L51-L65

This is not only problem about data types, but also type classes. Actually, It's even worse in case of type classes.

https://github.com/gcanti/fp-ts/blob/e708323cfcff0b4e013ecf6f90a00816fb943a64/src/Functor.ts#L19-L163

Why those things happens? Well, IMHO, I think this problem has been caused from two property of current way of encoding HKTs.

1. HKTs are separated based on their number of type parameters.

So we must write definition for all HKTs separately, by using something like function overloading(which makes code long, and verbose), instead of writing definition at once.

https://github.com/gcanti/fp-ts/blob/e708323cfcff0b4e013ecf6f90a00816fb943a64/src/StateT.ts#L164-L185

2. It's based on declaration merging & defunctionalization

Fundamental idea of current way of simulating HKTs is to express direct reference to HKTs by indirect reference(by using URI & URItoKind). As well as we choose to go around, it's natural to be suffered from boilerplate codes.

Desired Behavior

What I want is simpler & easier & readable encoding of HKTs. And to break down current limitation of this way of encoding HKTs(ex: It's hard to write HKTs that takes HKTs)

This will make this library more practical.

Suggested Solution

I've found some interesting trick that could be used to encoding HKTs,

How about using this trick to encoding HKTs? Indeed we need more research and investigations about this(ex: is this safe to use?, is there any limitation?, is there better way of using this trick? what else this trick can do?) but I think discussing about this would be valuable.

Who does this impact? Who is this for?

All of fp-ts users.

Additional context

• another example of using this trick - Generating eliminator for given constraint in typescript
• It seems to define kind system(or something like that) is possible with this trick.
• We can even use this trick to define type families!(and whenever self-appointed circular conditional type become stable, we can do whatever we wanted so far)

[raveclassic]

Nice trick, I can confirm it works for Functor and Maybe:

interface HKT {
    readonly param: unknown
    readonly result: unknown
}

type Apply<F extends HKT, A> = (F & { param: A })['result']

interface Functor<F extends HKT> {
    readonly map: <A, B>(fa: Apply<F, A>, f: (a: A) => B) => Apply<F, B>
}

interface Just<A> {
    readonly tag: 'Just'
    readonly value: A
}
const just = <A>(a: A): Just<A> => ({
    tag: 'Just',
    value: a,
})
interface Nothing {
    readonly tag: 'Nothing'
}
const nothing: Nothing = {
    tag: 'Nothing',
}
type Maybe<A> = Just<A> | Nothing
interface MaybeHKT extends HKT {
    result: Maybe<this['param']>
}

const functorMaybe: Functor<MaybeHKT> = {
    map: (fa, f) => (fa.tag === 'Nothing' ? fa : just(f(fa.value))),
}

// test

const double = (n: number): number => n * 2
const test1 = functorMaybe.map(nothing, double) // Maybe<number>
const test2 = functorMaybe.map(just(1), double) // Maybe<number>
const test3 = functorMaybe.map(just('foo'), double) // Error: string is not assignable to number

But how would you encode EitherHKT to produce Either<E, A>?

[ENvironmentSet]

You mean that How can I encode n-arg HKTs?(n > 1)

Currently, there is two of this(and I think these two way could be merged into one, since they are basically type-level currying and type-level n-arg function and as we know, they are fundamentally same)

1. Encoding by using tuple.

/** Let's assume that we have term-level implements of Either
    (it's okay to think it's same as fp-ts's one), named _Either. */
interface Either extends HKT {
  result: this['param'] extends [infer A, infer B] ? _Either<A, B> : never;
}

pros: Works Seamlessly & fit with intuition. cons: Hard to reuse(Partial application is hard), May not easily fit with type classes(type class encoding could be verbose).

2. Encoding by High-order HKTs

interface EitherC<A> extends HKT {
  result: _Either<A, this['param']>;
}
interface Either extends HKT {
  result: EitherC<this['param']>;
}

pros: Works perfectly with Type classes, easy to reuse. cons: Applying more than one arguments is verbose, definition could be complex(but I think there is solution for this, and I'm working on this)

3. Mix of these(<== I'm currently working on this)

interface EitherC<A> extends HKT {
  result: _Either<A, this['param']>;
}
interface Either extends HKT {
  result: this['param'] extends [infer A, infer B] ? _Either<A, B> : EitherC<this['param']>;
}

pros: Works perfectly with Type classes, easy to reuse. & Works Seamlessly & fit with intuition. cons: definition could be complex

Small Note:

• I'm testing & researching this trick in my small library, welltyped you can check more complex examples and use cases in there
• Actually, Functors are HKTs, too!(It means we can do so much(something like first-class type class) things rather than defining ADT with type parameters)

@raveclassic thx for your attention :)

[ENvironmentSet]

Another small note here, how about not to distinguish encoded version of HKT and normal one?

interface MaybeHKT extends HKT {
    result: this['param'] extends infer param ?
      { type: 'Just', value: param } | 'Nothing'
    : never;
}
type Maybe<A = 'indirectly'> = A extends 'indirectly' ? MaybeHKT : Apply<MaybeHKT, A>;

type Test = Maybe<number>;

[raveclassic]

@ENvironmentSet Thanks for explanation.

Encoding by High-order HKTs

This was exactly the first thing that came into my mind. But it doesn't work because Apply doesn't "apply" "twice". Tuple-based solution also does not work - type inference is broken for type arguments:

interface HKT {
    readonly param: unknown
    readonly result: unknown
}

type Apply<F extends HKT, A> = (F & { param: A })['result']

interface Functor<F extends HKT> {
    readonly map: <A, B>(fa: Apply<F, A>, f: (a: A) => B) => Apply<F, B>
}

// Either

interface Left<E> {
    readonly tag: 'Left'
    readonly left: E
}
const left = <E>(left: E): Left<E> => ({
    tag: 'Left',
    left,
})
interface Right<A> {
    readonly tag: 'Right'
    readonly right: A
}
const right = <A>(right: A): Right<A> => ({
    tag: 'Right',
    right,
})
type Either<E, A> = Left<E> | Right<A>

// functorEither
const double = (n: number) => n * 2

// Tuples
interface EitherHKTTuple extends HKT {
    readonly param: [unknown, unknown]
    readonly result: this['param'] extends [infer E, infer A] ? Either<E, A> : never
}
declare const functorEitherTuple: Functor<EitherHKTTuple>
// type is Either<unknown, unknown> but should be Either<string, number>
const test4 = functorEitherTuple.map(left('foo'), double)

// Higher-order HKT
interface EitherHKTHigherOrderC<A> extends HKT {
    readonly result: Either<this['param'], A>
}
interface EitherHKTHigherOrder extends HKT {
    readonly result: EitherHKTHigherOrderC<this['param']>
}
declare const functorEitherHigherOrder: Functor<EitherHKTHigherOrder>
// Error: Left<string> is not assignable to EitherHKTHigherOrderC<number>
const test5 = functorEitherHigherOrder.map(left('foo'), double)

[ENvironmentSet]

@raveclassic AFAIK, There is no Functor instance for Either(well, Biunctor is not the case., It's a 'functor' not a Functor). What we usually refer as 'Functor of Either' is actually 'Functor of Either A'(i.e Functor<Apply<Either, A>>) So you should write it like blow. then, you can see 'Encoding by High-order HKTs' work well.

interface EitherHKTC<A> extends HKT {
  result: Either<A, this['param']>;
}

interface EitherHKT extends HKT {
  result: EitherHKTC<this['param']>;
}

declare const getFunctorForEitherA: <A>() => Functor<Apply<EitherHKT, A>>;

// this works!
const test4 = getFunctorForEitherA().map(left('foo'), x => x);

Another small note here, I've just thought some awesome way to define HKT and it's curried version at one, with very small boilerplate. I'll post it later(I'm being chased by school assignment...).

[raveclassic]

@ENvironmentSet I'm not sure that always fixing left type of an Either (or generally any S, R, E types of any higher kind (* -> *, * -> * -> * etc)) would fit fp-ts design.

On the other hand this new encoding could help us dramatically reduce constraints on instance constants - we could drop URI field at all. This would dramatically simplify working with compositional types (FunctorComposition, ApplicativeComposition etc.) and monad transformers in the way that output of their constructors (getFunctorComposition, getReaderM etc.) could be used directly as instance constants. We could just pass result of getReaderM to pipeable etc.

@gcanti Please take a look:

import { none, option, Option, some } from 'fp-ts/lib/Option'
import { either, Either, left, right } from 'fp-ts/lib/Either'

interface HKT {
    readonly a: unknown
    readonly result: unknown
}
interface HKT2 extends HKT {
    readonly e: unknown
}

interface Compose11<F extends HKT, G extends HKT> extends HKT {
    readonly result: Kind<F, Kind<G, this['a']>>
}
interface Compose12<F extends HKT, G extends HKT2> extends HKT2 {
    readonly result: Kind<F, Kind2<G, this['e'], this['a']>>
}

type Kind<F extends HKT, A> = (F & { a: A })['result']
type Kind2<F extends HKT2, E, A> = (F & { e: E; a: A })['result']

interface Functor1<F extends HKT> {
    readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}
interface Functor2<F extends HKT2> {
    readonly map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}

function getFunctorComposition<F extends HKT, G extends HKT2>(F: Functor1<F>, G: Functor2<G>): Functor2<Compose12<F, G>>
function getFunctorComposition<F extends HKT, G extends HKT>(F: Functor1<F>, G: Functor1<G>): Functor1<Compose11<F, G>>
function getFunctorComposition<F extends HKT, G extends HKT>(
    F: Functor1<F>,
    G: Functor1<G>,
): Functor1<Compose11<F, G>> {
    return {
        map: (fga, f) => F.map(fga, (ga) => G.map(ga, f)),
    }
}

// Option
interface URIOption extends HKT {
    readonly result: Option<this['a']>
}
const functorOption: Functor1<URIOption> = option

// Either
interface URIEither extends HKT2 {
    readonly result: Either<this['e'], this['a']>
}
const functorEither: Functor2<URIEither> = either

// Option Either
const functorOptionEither = getFunctorComposition(functorOption, functorEither)

// compose even more! now it's possible to use FunctorComposition as Functor without extra URI
const functorOptionOptionOption = getFunctorComposition(
    getFunctorComposition(functorOption, functorOption),
    functorOption,
)

// tests
const double = (n: number) => n * 2
const test1 = functorOption.map(none, double) // Option<number>
const test2 = functorOption.map(some(123), double) // Option<number>
const test3 = functorOption.map(some('foo'), double) // Error

const test4 = functorEither.map(left('foo'), double) // Either<string, number>
const test5 = functorEither.map(right(123), double) // Either<never, number>

const test6 = functorOptionEither.map(none, double) // Option<Either<unknown, number>>
const test7 = functorOptionEither.map(some(left('foo')), double) // Option<Either<string, number>>
const test8 = functorOptionEither.map(some(right(123)), double) // Option<Either<never, number>>

const test9 = functorOptionOptionOption.map(none, double) // Option<Option<Option<number>>>
const test10 = functorOptionOptionOption.map(some(some(some(123))), double) // Option<Option<Option<number>>>
const test11 = functorOptionOptionOption.map(some(some(some('foo'))), double) // Error

[ENvironmentSet]

@raveclassic Great and It seems it could support what I want, too. 😄

Anyway, what about to use one single interface for Functor for DX?(indeed, it will internally use those many kinds of functors, just a proxy for them).

PoC is here:

interface Functor extends HKT {
    readonly result: this['a'] extends HKT2 ? 
      Functor2<this['a']>
      : this['a'] extends HKT ?
      Functor1<this['a']>
      : never;
}

I think we should discuss about way to reduce boilerplates (I know it's only way but you know, listed -N & -C suffixed definitions(not only type classes, but also HKT itself and other datatypes will be defined in this manner) are seems quite verbose, It would be great to find solution or at least, we should use them for only internal purpose, I mean, make user don't need to care about them.)

P.S. URI-prefix..? I'm not sure whether it's good... What If we just wrap both normal definition and HKT-encoded version in one type? Like I did before in this thread.

[raveclassic]

@ENvironmentSet

I think we should discuss about way to reduce boilerplates

Yes, me tool. All this mess with *C and *1, *2 typeclasses is very annoying. I tried to fix it but failed: https://github.com/gcanti/fp-ts/issues/1035

URI-prefix..? I'm not sure whether it's good...

This is only supposed to be used internally, end user fill always operate on ['result'].

type Maybe<A = 'indirectly'> = A extends 'indirectly' ? MaybeHKT : Apply<MaybeHKT, A>;

This is not an option because you can't define Maybe<'inderectly'> using string literal. Also I'm not sure whether it's a good idea to mix end type and such internal HKT encoding.

[ENvironmentSet]

@raveclassic that string was just an example, we can use some of helper type like blow to generator that 'marker'

export abstract class MakeVoid<Name extends keyof any> {
  protected readonly abstract _: {
    readonly [Tag in Name]: never;
  };
}

Anyway, I think It's a just problem of readability and notion of expression.(merging them doesn't effect to any kind of compile time-runtime behavior) Option and URIOption are fundamentally and conceptually same, right?(the only difference is way of instantiating, and I think we and users don't need to distinguish them by name) Then why don't we just abstract those small differences out? fmap for Either is just a bimap id for Either, but we abstracted out bimap and Bifunctor and use fmap of Functor. Is there any reason types shouldn't be same?

[gcanti]

@ENvironmentSet amazing trick, thanks for sharing

On the other hand this new encoding could help us dramatically reduce constraints on instance constants - we could drop URI field at all. This would dramatically simplify working with compositional types (FunctorComposition, ApplicativeComposition etc.) and monad transformers in the way that output of their constructors (getFunctorComposition, getReaderM etc.) could be used directly as instance constants. We could just pass result of getReaderM to pipeable etc.

@raveclassic I agree, this is very interesting, definitely something we should investigate further

[raveclassic]

@ENvironmentSet I'm playing with type + HKT unification and somehow it's not working for never type arg:

export interface HKT {
    readonly a: unknown
    readonly result: unknown
}

export type Kind<F extends HKT, A> = (F & { a: A })['result']

export interface Auto {
    readonly tag: unique symbol
}

export interface None {
    readonly tag: 'None'
}

export interface Some<A> {
    readonly tag: 'Some'
    readonly value: A
}

export type OptionType<A> = None | Some<A>
export interface OptionHKT extends HKT {
    readonly result: OptionType<this['a']>
}
export type Option<A = Auto> = A extends Auto ? OptionHKT : OptionType<A>

type Test = Option<never> // never - but should be OptionType<never>
export const none: Option<never> = {
    tag: 'None', // error - string is not assignable to never, wtf
}

Sidenote: I've finally realised where I've seen a similar thing - Rust's Associated Types! :D https://doc.rust-lang.org/book/ch19-03-advanced-traits.html?highlight=associated,types#advanced-traits. And if I'm not mistaken, OCaml uses the same technique to define its Functors

[ENvironmentSet]

@raveclassic FYI, Haskell(GHC) has same thing called 'Associated type synonym family'.

Anyway, it would be great if we find how to encode it in typescript, do you have an idea?

P.S. The problem you've shown seems quite complicated, I'll investigate what happened, too.(anyway, typescript had quite strange logic about conditional type overnever. If you search some related terms in typescript repo, you can see bunch of questions about their strangeness, and I think the solution about this might be there.)

[raveclassic]

FYI, Haskell(GHC) has same thing call 'Associated type synonym family'.

Oh, thanks, will take a look!

typescript had quite strange logic about conditional type over never

It doesn't even work for this:

export const some = <A>(a: A): Option<A> => ({
    tag: 'Some',
    value: a,
})

[raveclassic]

Also I think it's impossible to avoid overloadings for N-kind typeclasses because even if we can abstract input to a conditional type we still need to mess with kinds in the output:

export interface Apply1<F extends HKT> extends Functor1<F> {
    readonly ap: <A, B>(fab: Kind<F, (a: A) => B>) => (fa: Kind<F, A>) => Kind<F, B>
}

export interface Apply2<F extends HKT2> extends Functor2<F> {
    readonly ap: <E, A, B>(fab: Kind2<F, E, (a: A) => B>) => (fa: Kind2<F, E, A>) => Kind2<F, E, B>
}

export type Apply<F extends HKT> = F extends HKT2 ? Apply2<F> : F extends HKT ? Apply1<F> : never

///

export declare const sequenceT: <F extends HKT>(
    F: Apply<F>,
    // we need an overloading for each Kind, Kind2, Kind3 etc
    // to correctly produce output type
) => <A extends Kind<F, unknown>[]>(...args: A) => Kind<F, { [K in keyof A]: number }>

So summing up I would suggest to focus here on something we can really achieve at the moment - possibility of removing URI constraint from typeclasses and their instances. Unified N-kind support in a single type is still tricky. Unified type + HKT is still tricky.

[raveclassic]

@gcanti I've checked this new encoding for TraversableComposition without HKT-based versions, now this compiles

[gcanti]

@raveclassic the following snippet compiles too

function lift<F extends HKT>(F: Functor1<F>): <A, B>(f: (a: A) => B) => (fa: Kind<F, A>) => Kind<F, B> {
  return (f) => (fa) => 'WAT'
}

[ENvironmentSet]

@raveclassic

seems we have problem that some programs shouldn't be compiled are actually compiled when encoding them with new style. IMHO, 'absence of type of type' seems involved with this problem. since new encoding doesn't make type error directly and just result never when they're failed to be saturated, and type system allows never to exist(or be treated) in some special cases, this kinds of 'unacceptable programs' are accepted by type system regardless our actual intent.

Anyway, I have an idea about this, actually two but they're basically same.

What If we add 'type of type'(in Haskell, they're called kinds) to our type system? I've tested this idea in my personal project, and the whole working system was looked nice. (Actually, there was some cons of this which is sometime type of type makes type signature complex but it seems to be resolved if we do enough research)

P.S. this might be helpful to fix(or prevent or clarify) those odd evaluation about never type.

[raveclassic]

@gcanti Looks like Kind<F, B> resolves to unknown, so WAT is assignable to unknown :(

[raveclassic]

Yeah, looks like there's no way to get a structure type F from typeclass instances Functor1<F> because now there's no URI. This results in F being default { a: unknown, result: unknown } which in turn breaks Kind<F, B> because { a: B, result: unknown }['result'] is unknown.

*sigh*, we were so close...

@ENvironmentSet Any ideas how to fix this?

[ENvironmentSet]

@raveclassic It works if we remove extends HKT constraints from F and Functor1 and Kind and move to inside of Kind. but I'm not sure whether is right (this might cause some problem but they seems to be solved by type of types).

Can you find any problem about this approach?

Side note: ahh..., I hope this is not the end.....

[ryota-ka]

This is a little bit off the topic, but I believe it's worth mentioning here.

IIUC, currently we can't have higher-kinded-type-class-associated functions. Suppose we want to have a guard function in Alternative, which is an analogous to Haskell's Control.Monad.guard, with alt and zero. (typeless version: const guard = alt => p => p ? alt.of(undefined) : alt.zero();) With my limited knowledge this cannot be correctly typed at this moment due to the current HKT encoding.

I'm not sure this can also be resolved at the same time, but I hope so.

[gneuvill]

Do you guys know about https://github.com/strax/tshkt ?

[raveclassic]

@gneuvill Looks like it has exactly the same implementation as proposed here.

[gneuvill]

@raveclassic ok, sorry for the noise

[cruhl]

What is the feasibility of creating and pushing a proposal for HKTs within TypeScript itself? If any group of developers has a shot, this community seems like a good bet.

https://github.com/Microsoft/TypeScript/issues/1213

The label “help wanted” is encouraging!

[raveclassic]

@cruhl Actually that issue is my favorite in TypeScript tracker 😂

[waynevanson]

I haven't seen this discussed anywhere so I'm unsure if it's been considered as part of any solution related.

We could add a fixed phantom property type to all data structures, and use that value to say what HKT's it supports.

In the example below, I've only added FunctorWithIndex and not anything else. It also shows how we can add a type of HKT to globally declared structures.

// fp-ts/FunctorWithIndex
export interface FunctorWithIndex<E, A> {
  readonly index: E;
  readonly value: A;
}

// fp-ts/array
declare global {
  interface Array<T> {
    // and other HKT's in a UNION
    readonly $HKT: FunctorWithIndex<number, T>;
  }
}

// ... rest of fp-ts/array

We can import this module into a file and now have the phantom property exposed.

[ENvironmentSet]

Here is small news. TS officially admitted this trick as intended behavior and added test for this.

microsoft/TypeScript#40928

I think it would be worth now to investigate this more and find solution for constraining types.

[skeate]

I was playing around with this a bit, and think I might have some useful contributions.

I went back to encoding the type parameters with tuples, and found if you still restrict the number of type arguments, things can work, and I think it cleans things up a lot. You don't need FunctorN definitions; you can just use Functor. The arity-specific stuff can be abstracted to (potentially) reusable types.

Code Sandbox to mess with it

Highlights:

1. HKT now takes a parameter which represents the number of type parameters the HKT can take. For instance, interface MaybeHKT extends HKT<[_]> or interface EitherHKT extends HKT<[_, _]>.
2. No more URI or module declaration merging (already one of the benefits being discussed, but it's pretty nice)
3. Typeclass definition files seem a lot cleaner. What used to be overloads are now conditional types
4. Inference works very well.

I did find one case (after not working on this very long so there's bound to be others) where I was getting a type error (deriving map from Bifunctor), and a soft as-cast helped. I also largely only checked "happy path" code examples, though I did specifically try the lift example above and found it now errors, if you remove the extends HKT from Kind like @ENvironmentSet suggested.

(Aside: I also removed it from Functor and co, but the f => fa => "WAT" still correctly errors if you add it back into those. It only seems to be need to be removed from Kind itself.)

edit: poking around a bit more, this might have issues with abstracting over type classes :cry: I tried implementing guard based on @ryota-ka's post above (adding a few more type classes quickly) and this errors:

export const guard = <F>(F: Alternative<F>) => (p: boolean) =>
  p ? F.of(undefined) : F.zero();

because both of and zero are unions of incompatible types. But I guess you can kind of cheat it with overloads:

export function guard<F extends HKT<[_, _, _]>>(
  F: Alternative<F>
): (p: boolean) => Kind<F, [unknown, unknown, unknown]>;
export function guard<F extends HKT<[_, _]>>(
  F: Alternative<F>
): (p: boolean) => Kind<F, [unknown, unknown]>;
export function guard<F extends HKT<[_]>>(
  F: Alternative<F>
): (p: boolean) => Kind<F, [unknown]>;
export function guard<F extends HKT<[_]>>(F: Alternative<F>) {
  return (p: boolean) => (p ? F.of(undefined) : F.zero());
}

// elsewhere

const safeDiv = (x: number, y: number): M.Maybe<number> =>
  pipe(
    guard(M.alternative)(y !== 0),
    M.functor.map(() => x / y)
  );

:thinking:

[skeate]

Had an idea: since you have to specify your type parameter "slots" this way, maybe we could also use that to specify what kind of variance (if that's the right word) they should have? For instance,

export interface ReaderHKT extends HKT<[Contravariant, Invariant]> { ... }
export interface EitherHKT extends HKT<[Covariant, Invariant]> { ... }
export interface ReaderEitherHKT
  extends HKT<[Contravariant, Covariant, Invariant]> { ... }

(really not sure I'm using the right terminology for these, but hopefully you understand what I mean)

Demo

Essentially this should allow things like chainW to be the regular chain (or at least definable as part of the Chain typeclass itself, if we want to keep it separate). Defining typeclass functions doesn't get too much more complicated (chain before, after). This should also permit things like sequenceW though I haven't actually tried it yet.

I did some more typeclass abstracted coding and found it to be a bit more problematic, but still serviceable, I think. For example, writing EitherT, the function overload approach I used above for guard becomes far too cumbersome (you'd need separate definitions for each combination of variances, oof). My solution is to write the simple one-parameter case with valid types (which also seems to need more annotations than I'd like) and then hard cast it into the more general type.

[waynevanson]

Looks cool! Keep it up. I'll look more into this on a PC.

The word your looking for are typeclass. When the typeclass is implemented, its an instance of that typeclass (I believe).

[ENvironmentSet]

@skeate Nice idea, however, I have a question. What variants of type parameters of following type-level function are?

interface F extends HKT<[_, _]> {
  result: this['params'][0] extends true ? this['params'][1] : (x: this['params'][1]) => void
}

[ENvironmentSet]

Another Idea here: What if we use type parameter slots to specify kinds of type parameter? This would make narrowing type arguments in type-level function unnecessary and allow to check whether given call to type-level function is valid.

Example

[skeate]

What variants of type parameters of following type-level function are?

I was focused on functor hierarchy typeclasses, and didn't really consider the more general case like that. Maybe something like

interface F extends HKT<[_, _]> {
  readonly variances: [
    Invariant,
    this["params"][0] extends true ? Covariant : Contravariant
  ];
  result: this["params"][0] extends true
    ? this["params"][1]
    : (x: this["params"][1]) => void;
}

? To be honest I'm not really sure how one would even use F...

I think this could generalize to any kind of information we wanted to track about a given type parameter, since we can just tack on more in the HKT interface. Even have things extend HKT to add features, for example if we have some things that care about variance and some that don't:

type ValidParamCounts = 1 | 2 | 3;
type TypeVariances =
  | [Variance]
  | [Variance, Variance]
  | [Variance, Variance, Variance];
type TypeConstraints =
  | [unknown]
  | [unknown, unknown]
  | [unknown, unknown, unknown];

export interface HKT<
  Params extends ValidParamCounts,
  Constraints extends TypeConstraints = TypeConstraints & { length: Params }
> {
  readonly params: Constraints;
  readonly result: unknown;
}

export interface VariantHKT<
  Params extends ValidParamCounts,
  Variances extends TypeVariances,
  Constraints extends TypeConstraints = TypeConstraints & { length: Params }
> extends HKT<Params, Constraints> {
  readonly variances: Variances;
}

To be honest I can't really think of other things that might be useful to track though. Maybe you have a generalized collection HKT that wants to know if its elements are unique or something (to differentiate Set from Multiset, say). Not sure. But the power is there!

[brettmitchelldev]

I've been playing around with this idea in a personal library for a while now, and I've got a couple suggestions that I think might add to the conversation:

1. If you want to use the current solution with a type that constrains its type parameters with an extends clause, you need to introduce a conditional type to ensure the types match. This can get messy for complex types.
2. Using tuples specifically to represent positional arguments is highly useful in some contexts, but confusing in others, making it inconvenient to be forced to use them at the top level of the HKT. Consider a kind that encodes a variadic function with a parameterized return type that depends on the type of the variadic argument list (simplified from a use case in my current work). The resulting HKT might look something like this:

   interface VariadicParameterizedReturnHKT extends HKT <[_, _]> {
   result: this['params'][0] extends [...infer Arguments] ? VariadicParameterizedReturn <Arguments, this['params'][1]> : never;
   }

   This isn't very readable, and specifying that this['params'][0] is supposed to be a tuple rather than anything else is a bit clunky.

3. Which brings me to my third point: the current constraint technique does not provide a mechanism for constraining the type of type parameters. Whenever we run across a situation where the concrete type constrains its parameter with an extends clause, we are forced to use a conditional type on our type parameters in the implementing HTK.

My current solution solves these issues with the following:

1. Indirect type parameter application using the same this polymorphism that allows the present implementation.
2. Type parameter constraints stored in a separate field from params.

Note: My terminology is a bit different here. From my understanding, TypeConstructor and ApplyTypeConstructor are correct terms to use here, but please let me know if it makes more sense to use HKT and Kind; I'd like to use correct terminology in my project.

From the following snippet, you can see that TypeConstructor is the same as HKT above with two additional properties: constraint and apply. constraint stores the type constraints on the parameters applicable to the TypeConstructor, while apply is used exclusively to provide type parameters to the TypeConstructor at the time of application.

apply is necessary (rather than using params: Constraint), because if any type other than unknown were to be used as the initial value of params, the declaration merging step used to apply type parameters would not resolve correctly for all types. With this strategy, params will be strictly of type constraint in the definition of the TypeConstructor (providing type hints while working with the type and without needing a manual conditional type), and strictly of type apply at the point of parameter application.

ApplyTypeConstructor restricts the parameters that are allowed to be passed in to a TypeConstructor based on the constraint property of the TypeConstructor, which causes the compiler to show an error for any instance of incorrectly applied type parameters. Unfortunately, this is not picked up very well by the TS language service, so VSCode will not autocomplete property names as you type out parameters to ApplyTypeConstructor, but you will be prevented from passing illegal arguments.

I'm not yet convinced mine is a bulletproof technique, but hopefully it adds something to the discussion.

export interface TypeConstructor <Constraint = unknown> {
  constraint: Constraint;
  params: this['apply'] extends this['constraint']
    ? this['apply'] : this['constraint'];
  apply: unknown;
  result: unknown;
}

export type ApplyTypeConstructor <
  Kind extends TypeConstructor <any>,
  Params extends Kind['constraint'],
> = (Kind & { apply: Params })['result'];

This implementation allows for things like the following, which I suspect may apply nicely to some of the edge cases mentioned above.

interface TypeWithConstrainedParams <P1 extends number, P2 extends { x: string; y: number }> {
  p1: P1;
  p2: P2;
}

interface TWCPKind1 extends TypeConstructor <[number, { x: string; y: number }]> {
  result: TypeWithConstrainedParams <this['params'][0], this['params'][1]>;
}

// As opposed to with previous solution

interface TWCPKind2 extends HKT <[_, _]> {
  result: this['params'] extends [number, { x: string; y: number }] ? TypeWithConstrainedParams <this['params'][0], this['params'][1]> : never;
}

// This easy-to-make typo silently resolves to never
interface TWCPKind3 extends HKT <[_, _]> {
  result: this['params'] extends [number] ? TypeWithConstrainedParams <this['params'][0], this['params'][1]> : never;
}

// But such a situation is more difficult to contrive with the alternative implementation, since 'params' is automatically of the expected type.
interface TWCPKind4 extends TypeConstructor <[number, { x: string; y: number }]> {
  result: this['params'] extends [number, { y: number }] ? TypeWithConstrainedParams <this['params'][0], this['params'][1]> : never;
}

// And mistyping when writing a type naturally shows a compiler error.
interface TWCPKind5 extends TypeConstructor <[number, { x: string; y: number }]> {
  result: TypeWithConstrainedParams <this['params'][0], this['params'][1]['x']>;
}

// Finally, mis-applying type parameters shows a compiler error with clean, actionable feedback.
type ResultBad = ApplyTypeConstructor <TWCPKind1, [123, { x: number; y: string }]>;
// But types may be further specified as long as they extend the constraint requirement.
type ResultGood = ApplyTypeConstructor <TWCPKind1, [123, { x: 'Applied!'; y: 456 }]>;

EDIT: I just noticed that this is very similar to the constraint technique in the link provided here https://github.com/gcanti/fp-ts/issues/1208#issuecomment-778936386. Hopefully there's something that ends up being useful and not just noise in the conversation. :smiley:

[brettmitchelldev]

Some new functionality I came up with: Inline partial application for TypeConstructors that take tuple parameters using interface extension.

// Required to spread the result of PartialTuple and RelaxedTuple
type CoerceArray <T> = T extends any[] ? T : never;
// Required to allow specifying tuple with length less than constraint
type PartialTuple <T extends any[]> = CoerceArray <{ [K in keyof T]?: T[K] }>;
// Required to allow inferring rest params
type RelaxedTuple <T extends any[]> = CoerceArray <{ [K in keyof T]: any }>;

export interface ApplyTypeConstructorPartial <
  Kind extends TypeConstructor <any[]>,
  Params extends PartialTuple <Kind['constraint']>,
> extends TypeConstructor <Kind['constraint'] extends [...RelaxedTuple <Params>, ...infer Rest] ? Rest : never> {
  result: ApplyTypeConstructor <Kind, [...Params, ...this['params']]>;
}

Some examples:

// Basic type constructor that just returns its parameters
interface T1 extends TypeConstructor <[any, string, boolean]> { result: this['params'] }

// Directly applied with all required type parameters
type FullyApplied1 = ApplyTypeConstructor <T1, ['foo', 'bar', true]>;
// => ['foo', 'bar', true]

// Apply one type parameter at a time
type P1 = ApplyTypeConstructorPartial <T1, [number]>;
type P2 = ApplyTypeConstructorPartial <P1, ['123']>;
type FullyApplied2 = ApplyTypeConstructor <P2, [true]>;
// => [number, '123', true]

// Apply two type parameters at a time
type P3 = ApplyTypeConstructorPartial <T1, [number, '123']>;
type FullyApplied3 = ApplyTypeConstructor <P3, [true]>;
// => [number, '123', true]

// Restricts parameters based on provided constraint
type P4 = ApplyTypeConstructorPartial <T1, [number, '123', true, 'extra']>;
// Type '[number, "123", true, "extra"]' does not satisfy the constraint '[any?, string?, boolean?]'.
//   Source has 4 element(s) but target allows only 3.

// Partially applied type constructors also have valid constraints
type P5 = ApplyTypeConstructorPartial <T1, [number]>;
type P6 = ApplyTypeConstructorPartial <P5, ['123', 'not a boolean']>;
// Type '["123", "not a boolean"]' does not satisfy the constraint '[string?, boolean?]'.
//   Types of property '1' are incompatible.
//     Type 'string' is not assignable to type 'boolean'.

There might be a way to combine this partial application technique with the standard ApplyTypeConstructor using a conditional type to provide automatic currying, but I haven't tried that yet.

[brettmitchelldev]

FWIW, I've published my HKT implementation based on the trick discussed here on NPM. Not sure if you folks will want to use it (I've added features and maybe its heavier than this library would want), but I thought I'd drop a link here just in case.

https://www.npmjs.com/package/@miscellany/types

Feel free to copy over from the repo if you don't want to add it as a dependency.

https://gitlab.com/brett-mitchell-dev/miscellany/types/-/tree/master

[gcanti]

@brettmitchelldev thanks, I'm a bit lost, could you please provide an example containing:

• the type-class Functor
• Functor instances for Option and/or Either
• the lift function above

[brettmitchelldev]

Here's my take on those structures (hopefully in faithful fp-ts style :stuck_out_tongue:) using the HKT implementation I linked above. I hope this is helpful, let me know if you need to see some more examples. Please note this is a very new library and I've pushed up some patches already, so make sure to use 1.0.4 when playing around with it:

I've written the following snippets so they work when placed inline in the same file:

Functor typeclass and lift:

import { TCtor, ApI } from '@miscellany/types/hkt';

type Init <T extends any[] | readonly any[]> =
  T extends [...infer I, any] ? I : never;

type MapTo <FunctorType extends TCtor <any[]>, Param, Return> = (
  <
    WithParam extends [...Init <FunctorType['paramConstraint']>, Param],
    // No need for arity-specific MapTo cases. Just infer leading terms here.
    // Functors are not restricted to any set number of parameters this way.
    // Coercion to param constraint could be done with a conditional type in
    //  ApI below, but I thought doing that here with a default was a bit cleaner.
    WithReturn extends FunctorType['paramConstraint'] = [...Init <WithParam>, Return],
  >
  (functorInstance: ApI <FunctorType, WithParam>) =>
    ApI <FunctorType, WithReturn>
);

interface Functor <FunctorType extends TCtor <any[]>> {
  map:
    <Param, Return>
    (fn: (param: Param) => Return) =>
      MapTo <FunctorType, Param, Return>;
}

function lift
  <FunctorType extends TCtor <any[]>>
  (f: Functor <FunctorType>)
  : <P, R> (fn: (p: P) => R) => MapTo <FunctorType, P, R> {
    return f.map;
  }

Either and associated Functor typeclass instance

namespace E {
  export interface Left <A> {
    readonly tag: 'Left';
    readonly left: A;
  }
  export interface Right <B> {
    readonly tag: 'Right';
    readonly right: B;
  }

  export type Either <A, B> = Left <A> | Right <B>;
  export interface EitherCtor extends TCtor <[any, any]> {
    result: Either <this['params'][0], this['params'][1]>;
  }

  export const left  = <A> (left: A): Left <A> => ({ tag: 'Left',  left });
  export const right = <B> (right: B): Right <B> => ({ tag: 'Right', right });

  export const functor: Functor <EitherCtor> = {
    map:
      <Param, Return> (fn: (param: Param) => Return) =>
      <L> (eitherInstance: Either <L, Param>)
      : Either <L, Return> => (
        eitherInstance.tag === 'Left'
          ? eitherInstance
          : right (fn (eitherInstance.right))
      ),
  };
}

Using the above:

const mapLen = E.functor.map ((s: string) => s.length);

const r1 = mapLen (E.right (123));
// Argument of type 'Right<number>' is not assignable to parameter of type 'Either<any, string>'.
//   Type 'Right<number>' is not assignable to type 'Right<string>'.
//     Type 'number' is not assignable to type 'string'.

const r2 = mapLen (E.right ('123'));
// => Either <any, number>
const r3 = mapLen (E.left (123));
// => Either <any, number>

const liftedMapLen = lift (E.functor) ((s: string) => s.length);

// Not totally sure why the last error line is not present here as it is above.
const r4 = liftedMapLen (E.right (123));
// Argument of type 'Right<number>' is not assignable to parameter of type 'Either<any, string>'.
//   Type 'Right<number>' is not assignable to type 'Right<string>'.

const r5 = liftedMapLen (E.right ('123'));
// => Either <any, number>
const r6 = liftedMapLen (E.left (123));
// => Either <any, number>

[kalda341]

While a lot of this is over my head if I'm being honest, the encoding shown here: https://www.matechs.com/blog/encoding-hkts-in-typescript-once-again looks really nice, and I find it much easier to wrap my head around.