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.

fp-ts/src/Option.ts

Lines 51 to 65 in e708323

	declare module './HKT' {
	interface URItoKind<A> {
	readonly Option: Option<A>
	}
	}
	/**
	* @since 2.0.0
	*/
	export const URI = 'Option'
	/**
	* @since 2.0.0
	*/
	export type URI = typeof URI

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

fp-ts/src/Functor.ts

Lines 19 to 163 in e708323

	export interface Functor<F> {
	readonly URI: F
	readonly map: <A, B>(fa: HKT<F, A>, f: (a: A) => B) => HKT<F, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface Functor1<F extends URIS> {
	readonly URI: F
	readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface Functor2<F extends URIS2> {
	readonly URI: F
	readonly map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface Functor2C<F extends URIS2, E> {
	readonly URI: F
	readonly _E: E
	readonly map: <A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface Functor3<F extends URIS3> {
	readonly URI: F
	readonly map: <R, E, A, B>(fa: Kind3<F, R, E, A>, f: (a: A) => B) => Kind3<F, R, E, B>
	}
	/**
	* @since 2.2.0
	*/
	export interface Functor3C<F extends URIS3, E> {
	readonly URI: F
	readonly _E: E
	readonly map: <R, A, B>(fa: Kind3<F, R, E, A>, f: (a: A) => B) => Kind3<F, R, E, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface Functor4<F extends URIS4> {
	readonly URI: F
	readonly map: <S, R, E, A, B>(fa: Kind4<F, S, R, E, A>, f: (a: A) => B) => Kind4<F, S, R, E, B>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition<F, G> {
	readonly map: <A, B>(fa: HKT<F, HKT<G, A>>, f: (a: A) => B) => HKT<F, HKT<G, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorCompositionHKT1<F, G extends URIS> {
	readonly map: <A, B>(fa: HKT<F, Kind<G, A>>, f: (a: A) => B) => HKT<F, Kind<G, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorCompositionHKT2<F, G extends URIS2> {
	readonly map: <E, A, B>(fa: HKT<F, Kind2<G, E, A>>, f: (a: A) => B) => HKT<F, Kind2<G, E, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorCompositionHKT2C<F, G extends URIS2, E> {
	readonly map: <A, B>(fa: HKT<F, Kind2<G, E, A>>, f: (a: A) => B) => HKT<F, Kind2<G, E, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition11<F extends URIS, G extends URIS> {
	readonly map: <A, B>(fa: Kind<F, Kind<G, A>>, f: (a: A) => B) => Kind<F, Kind<G, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition12<F extends URIS, G extends URIS2> {
	readonly map: <E, A, B>(fa: Kind<F, Kind2<G, E, A>>, f: (a: A) => B) => Kind<F, Kind2<G, E, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition12C<F extends URIS, G extends URIS2, E> {
	readonly map: <A, B>(fa: Kind<F, Kind2<G, E, A>>, f: (a: A) => B) => Kind<F, Kind2<G, E, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition21<F extends URIS2, G extends URIS> {
	readonly map: <E, A, B>(fa: Kind2<F, E, Kind<G, A>>, f: (a: A) => B) => Kind2<F, E, Kind<G, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition2C1<F extends URIS2, G extends URIS, E> {
	readonly map: <A, B>(fa: Kind2<F, E, Kind<G, A>>, f: (a: A) => B) => Kind2<F, E, Kind<G, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition22<F extends URIS2, G extends URIS2> {
	readonly map: <FE, GE, A, B>(fa: Kind2<F, FE, Kind2<G, GE, A>>, f: (a: A) => B) => Kind2<F, FE, Kind2<G, GE, B>>
	}
	/**
	* @since 2.0.0
	*/
	export interface FunctorComposition22C<F extends URIS2, G extends URIS2, E> {
	readonly map: <FE, A, B>(fa: Kind2<F, FE, Kind2<G, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind2<G, E, B>>
	}
	/**
	* @since 2.2.0
	*/
	export interface FunctorComposition23<F extends URIS2, G extends URIS3> {
	readonly map: <FE, R, E, A, B>(fa: Kind2<F, FE, Kind3<G, R, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind3<G, R, E, B>>
	}
	/**
	* @since 2.2.0
	*/
	export interface FunctorComposition23C<F extends URIS2, G extends URIS3, E> {
	readonly map: <FE, R, A, B>(fa: Kind2<F, FE, Kind3<G, R, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind3<G, R, E, B>>
	}

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.

fp-ts/src/StateT.ts

Lines 164 to 185 in e708323

	export function getStateM<M extends URIS3>(M: Monad3<M>): StateM3<M>
	export function getStateM<M extends URIS3, E>(M: Monad3C<M, E>): StateM3C<M, E>
	export function getStateM<M extends URIS2>(M: Monad2<M>): StateM2<M>
	export function getStateM<M extends URIS2, E>(M: Monad2C<M, E>): StateM2C<M, E>
	export function getStateM<M extends URIS>(M: Monad1<M>): StateM1<M>
	export function getStateM<M>(M: Monad<M>): StateM<M>
	export function getStateM<M>(M: Monad<M>): StateM<M> {
	return {
	map: (fa, f) => (s) => M.map(fa(s), ([a, s1]) => [f(a), s1]),
	of: (a) => (s) => M.of([a, s]),
	ap: (fab, fa) => (s) => M.chain(fab(s), ([f, s]) => M.map(fa(s), ([a, s]) => [f(a), s])),
	chain: (fa, f) => (s) => M.chain(fa(s), ([a, s1]) => f(a)(s1)),
	get: () => (s) => M.of([s, s]),
	put: (s) => () => M.of([undefined, s]),
	modify: (f) => (s) => M.of([undefined, f(s)]),
	gets: (f) => (s) => M.of([f(s), s]),
	fromState: (sa) => (s) => M.of(sa(s)),
	fromM: (ma) => (s) => M.map(ma, (a) => [a, s]),
	evalState: (ma, s) => M.map(ma(s), ([a]) => a),
	execState: (ma, s) => M.map(ma(s), ([_, s]) => s)
	}
	}

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: #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 over never. 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,
})