Fp-ts: 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

1. 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).

1. 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)

1. 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.

[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.