fp-ts Tuple-powered HKT encoding

🚀 Feature request

Current Behavior

Currently, when implementing a new typeclass or an instance you'll likely have to handwrite many overloads.

Desired Behavior

Ideally, we'd define these things just once.

Who does this impact? Who is this for?

All Users

Describe alternatives you've considered

Mainly the 1.x of version of fp-ts (we use it at my day job), and briefly the current version of fp-ts.

Jul 22 '20 03:07 TylorS

@TylorS I couldn't make that work with typescript@next (4.1.0.dev.blabla). e.g.

const array: Functor<"array"> = {
  map: (f, F) => F.map(f),
};

complains Type 'B' is not assignable to type 'Last<[...Pop<TypeParamsOf<F>>, B]>'. So TS couldn't infer that Last[...X, Y] to be Y, using ts-toolbelt types.

I also wasn't sure what Type in Type<T, [....Pop<TypeParamsOf<F>>, B]> was, I assumed it to be a Kind.

Perhaps you have a fully functional gist that I can play with? That'd be really helpful.

Aug 30 '20 13:08 anilanar

Hey @anilanar, I don't have full examples just yet but I have a library that I toyed around with that does part of this. https://github.com/TylorS/hkt-ts

After working with it a little, I don't know that I find it particularly compelling from my implementation at least, but maybe another can iterate on it. For now, I'm building libraries atop fp-ts.

Sep 12 '20 01:09 TylorS

Just as a general info I also tried this approach and at the end decided not to follow with it because my point was removing the need of both overloads and multiple typeclasses definitions. I ended up with a different approach that draws partial inspiration from https://github.com/gcanti/fp-ts/issues/1035 in having a parameter to encode constraints, the code I am working on can be found at https://github.com/Matechs-Garage/matechs-effect/tree/master/packages/core/src/Prelude/HKT (it targets TS 4.1 because it uses recursive types to define combined URIS for transformers)

Sep 14 '20 09:09 mikearnaldi

@mikearnaldi I've actually done some looking through there already. I've been keeping a healthy eye on your Effect work since you gave the very useful introduction at SimSpace (where I currently work, but am soon leaving). I also saw you were present at John De Goes' presentation on ZIO-Prelude and the law-based HKT encodings, and I think it's really cool you're working on similar in TypeScript. Have you run into any interesting issues doing that port?

Sep 14 '20 20:09 TylorS

@TylorS You are correct I was at the presentation and apart from that presentation John has been really nice in giving some color around principles of both prelude and zio in the past months.

The most interesting aspect that raised my initial curiosity was the concept of using a "lattice" instead of a hierarchy to design the set of typeclasses, I have never liked the forced subtyping relationship that is imposed in the classical approach for example I remember clearly a slack thread with @gcanti where we both argued Monad & Applicative should really be separated things and that there is no general theoretical relationship between the 2 in cat theory apart from a monad giving rise to an "applicative functor" (lax-monoidal functor with tensorial strength). At the very end I believe this encoding of typeclasses is actually more theoretically correct).

Another aspect that attracted me was the usage of variance that has been a controvertial topic for quite a while in the FP community and by some it is not very welcome, I have to say most of the "strict" approach is due to the haskell inspiration where there is no subtyping whatsoever, I generally believe FP in the context of a language is not 100% portable to another and I do prefer embracing variance (one example of this preference is the design of Effect where every parameter allow variance).

The above to explain my thinking and baseline in starting the TypeScript port, clearly it sounded quite insane at the beginning given the lack of both variance annotations and HKTs in TS that have been the worst nightmare I had to go through, basically I spent a month only to get to a point where I was finally able to encode parameter variance & dynamic constraints for the typeclasses, I was also attempting to make parameters variadic but that really didn't work out for inference reasons so at the end I opted for a fixed set of 15 parameters that should give enough space.

Where variadic tuples and recursive types worked out is instead in designing the Kind's URI, that allows to write generic typeclass transformers

Sep 15 '20 06:09 mikearnaldi

Thanks for taking the time to reply back. I'm quite sure the variance was difficult, and I hope to understand how you solved it at some point 😄 .

What do you think about creating a library with "just" the HKT encoding and the law-based typeclasses? Similar in goals to my previously mentioned hkt-ts lib, as I think it'd be great to have a shareable encoding to interoperate between many different libraries that may not want/need all of the additional components of either fp-ts or the many many features also included in your matechs libraries. I'd be very interested in helping to maintain it if that's of any concern.

Sep 16 '20 14:09 TylorS

I thought to do it but at the end decided it wasn't a good idea, the reason being the HKT encoding and usage is still quite painful & has a lot of type params, that is 100% fine for a system that has full fledged modules and typeclasses but for specialised things I still prefer to make specific smaller HKTs with 2-3 params so the specific interfaces are not affected by the verbosity

Sep 17 '20 09:09 mikearnaldi

@gcanti Is working with the new matech hkt implementation, experimenting with HKD, etc in the hkt-3.0 branch. Since this issue touches on the tuple approach that I have been using over in fun and I'm also migrating to the nice "this" based hkt I figured it might be nice to renew something I've been mucking with locally wrt hkt tuples, variance, and ease of use. Currently, I'm looking at the following HKT implementation. Here is the current fp-ts run that I'm basing the "in" "out" "inout" jargon on. Following is another idea:

// This is not exported to keep it from ever being accidentally referenced
declare const PhantomType: unique symbol;

/**
 * @experimental
 * Holds a type level value to keep it around for better inference 
 */
export interface Hold<A> {
  readonly [PhantomType]?: A;
}

/**
 * @experimental
 * Typeclass is a type constrained held type, specifically constrained
 * to a "Kind" (ie. type level type)
 */
export type TypeClass<U extends Kind> = Hold<U>;

/**
 * Splits the different type level substitutions into tuples
 * based on variance.
 */
export type Substitutions = {
  readonly in: { [K: number]: unknown };
  readonly out: { [K: number]: unknown };
  readonly inout: { [K: number]: unknown };
};

// Unnecessary type aliases for "prettier" URI implementations
export type In<T extends Kind, N extends keyof T["in"]> = T["in"][N];
export type Out<T extends Kind, N extends keyof T["out"]> = T["out"][N];
export type InOut<T extends Kind, N extends keyof T["inout"]> = T["inout"][N];

/**
 * Kind is an interface that can be extended
 * to retrieve inner types using "this".
 */
export interface Kind extends Substitutions {
  readonly type?: unknown;
}

/**
 * Substitute is a substitution type, taking a Kind implementation T and
 * substituting it with types as defined by the evaluation of T
 * with the values in a Substitutions object S
 */
export type Substitute<T extends Kind, S extends Substitutions> = T extends
  { readonly type: unknown } ? (T & S)["type"]
  : { readonly T: T; readonly S: () => S };
  
/**
 * $ is an alias over Substitute that makes the substitution a little
 * slimmer
 */
export type $<
  T extends Kind,
  O extends Substitutions["out"],
  I extends Substitutions["in"],
  IO extends Substitutions["inout"],
> = Substitute<T, { out: O; in: I; inout: IO }>;

An algebraic structure is then implemented in a similar manner to the existing "type classes":

import type { $, Kind, TypeClass } from "./kind.ts";

/**
 * Functor
 * https://github.com/fantasyland/static-land/blob/master/docs/spec.md#functor
 */
export interface Functor<U extends Kind> extends TypeClass<U> {
  readonly map: <A, I>(
    fai: (a: A) => I,
  ) => <B, C, D, E, F>(
    ta: $<U, [A, B, C], [D, E], [F]>,
  ) => $<U, [I, B, C], [D, E], [F]>;
}

And an implementation of an algebraic data type is like this:

import type { $, Kind, Out } from "./kind.ts";
import type * as T from "./functor.ts";

export type Left<L> = { tag: "Left"; left: L };

export type Right<R> = { tag: "Right"; right: R };

export type Either<L, R> = Left<L> | Right<R>;

export interface URI extends Kind {
  readonly type: Either<Out<this, 1>, Out<this, 0>>;
}

export interface RightURI<B> extends Kind {
  readonly type: Either<B, Out<this, 0>>;
}

export function left<E = never, A = never>(left: E): Either<E, A> {
  return ({
    tag: "Left",
    left,
  });
}

export function right<E = never, A = never>(right: A): Either<E, A> {
  return ({
    tag: "Right",
    right,
  });
}

export const Functor: T.Functor<URI> = {
  map: (fai) => (ta) => ta.tag === "Left" ? ta : right(fai(ta.right)),
};

export const getRightFunctor = <L>(): T.Functor<RightURI<L>> => ({ map: Functor.map });

I'd appreciate any feedback you guys have to offer. Another benefit of this new hkt encoding (that doesn't matter much to matech of fp-ts) is that it survives translation from Deno to Node by the dnt tool. The declare module HKT implementation did not : /

EDIT: I have yet to settle on forcing variance based on the Substitutions object in the Substitute type but it seems trivial to implement (famous last words).

Sep 26 '22 20:09 baetheus

@baetheus thanks for sharing. I was discussing this kind of tuple-based encoding with @mikearnaldi a couple of days ago, my main drive being to come up with something that would allow adding a new (inout / in / out) param in the future without breaking changes.

However adding such a param would mean adding a new generic to all signatures and unfortunately this seems a breaking change nonetheless (at the call site).

This tuple-based encoding would also affect readability (which is already quite bad)

ideal:

export interface Apply<F extends TypeLambda> extends Functor<F> {
  readonly ap: <A>(
    fa: Kind<F, A>
  ) => <B>(self: Kind<F, (a: A) => B>) => Kind<F, B>
}

current:

export interface Apply<F extends TypeLambda> extends Functor<F> {
  readonly ap: <S, R2, O2, E2, A>(
    fa: Kind<F, S, R2, O2, E2, A>
  ) => <R1, O1, E1, B>(self: Kind<F, S, R1, O1, E1, (a: A) => B>) => Kind<F, S, R1 & R2, O1 | O2, E1 | E2, B>
}

proposed:

export interface Apply<F extends TypeLambda> extends Functor<F> {
  readonly ap: <S, R2, A, E2, O2>(
    fa: Kind<F, [A, E2, O2], [R2], [S]>
  ) => <R1, B, E1, O1>(
    self: Kind<F, [(a: A) => B, E1, O1], [R1], [S]>
  ) => Kind<F, [B, E1 | E2, O1 | O2], [R1 & R2], [S]>
}

Another example: getApComposition (Apply module)

ideal:

export const getApComposition =
  <F extends TypeLambda, G extends TypeLambda>(F: Apply<F>, G: Apply<G>) =>
  <A>(
    fa: Kind<F, Kind<G, A>>
  ): (<B>(
    self: Kind<F, Kind<G, (a: A) => B>>
  ) => Kind<F, Kind<G, B>>) => {
    return ...
  }

current:

export const getApComposition =
  <F extends TypeLambda, G extends TypeLambda>(F: Apply<F>, G: Apply<G>) =>
  <FS, FR2, FO2, FE2, GS, GR2, GO2, GE2, A>(
    fa: Kind<F, FS, FR2, FO2, FE2, Kind<G, GS, GR2, GO2, GE2, A>>
  ): (<FR1, FO1, FE1, GR1, GO1, GE1, B>(
    self: Kind<F, FS, FR1, FO1, FE1, Kind<G, GS, GR1, GO1, GE1, (a: A) => B>>
  ) => Kind<F, FS, FR1 & FR2, FO1 | FO2, FE1 | FE2, Kind<G, GS, GR1 & GR2, GO1 | GO2, GE1 | GE2, B>>) => {
    return ...
  }

proposed

export const getApComposition =
  <F extends TypeLambda, G extends TypeLambda>(F: Apply<F>, G: Apply<G>) =>
  <FS, FR2, FO2, FE2, GS, GR2, GO2, GE2, A>(
    fa: Kind<F, [Kind<G, [A, GE2, GO2], [GR2], [GS]>, FE2, FO2], [FR2], [FS]>
  ): (<FR1, FO1, FE1, GR1, GO1, GE1, B>(
    self: Kind<F, [Kind<G, [(a: A) => B, GE1, GO1, FE1, FO1], [GR1], [GS]>], [FR1], [FS]>
  ) => Kind<F, [Kind<G, [B, GE1 | GE2, GO1 | GO2], [GR1 & GR2], [GS]>, FE1 | FE2, FO1 | FO2], [FR1 & FR2], [FS]>) => {
    return ...
  }

Another (minor?) technical con is defining more complex type lambdas like ValidatedTypeLambda (Either module)

current

export interface ValidatedTypeLambda<F extends TypeLambda, E> extends TypeLambda {
  readonly type: Kind<F, this['InOut1'], this['In1'], this['Out3'], E, this['Out1']>
}

proposed

export interface ValidatedTypeLambda<F extends TypeLambda, E> extends TypeLambda {
  readonly type: Kind<F, { [K in keyof this['out']]: K extends '1' ? E : this['out'][K] }, this['in'], this['inout']>
}

EDIT: btw this was my experimental tuple-based encoding

export declare const URI: unique symbol

export interface TypeClass<F extends TypeLambda> {
  readonly [URI]?: F
}

export interface TypeLambda {
  readonly InOut: ReadonlyArray<unknown>
  readonly In: ReadonlyArray<unknown>
  readonly Out: ReadonlyArray<unknown>
  readonly type?: unknown
}

export type Kind<F extends TypeLambda, InOut, In, Out> = F extends {
  readonly type: unknown
}
  ? (F & {
      readonly InOut: InOut
      readonly In: In
      readonly Out: Out
    })['type']
  : {
      readonly F: F
      readonly InOut: (_: InOut) => InOut
      readonly In: (_: In) => void
      readonly Out: () => Out
    }

export interface Functor<F extends TypeLambda> extends TypeClass<F> {
  readonly map: <A, B>(
    f: (a: A) => B
  ) => <S, R, E, O>(self: Kind<F, [S], [R], [A, E, O]>) => Kind<F, [S], [R], [B, E, O]>
}

import type { Either } from 'fp-ts/Either'

export interface EitherTypeLambda extends TypeLambda {
  readonly type: Either<this['Out'][1], this['Out'][0]>
}

declare const FunctorEitherTypeLambda: Functor<EitherTypeLambda>

// Functor<EitherTypeLambda>.map: <A, B>(f: (a: A) => B) => <S, R, E, O>(self: Either<E, A>) => Either<E, B>
FunctorEitherTypeLambda.map

export interface ValidatedTypeLambda<F extends TypeLambda, E> extends TypeLambda {
  readonly type: Kind<F, this['InOut'], this['In'], { [K in keyof this['Out']]: K extends '1' ? E : this['Out'][K] }>
}

declare const FunctorValidated: Functor<ValidatedTypeLambda<EitherTypeLambda, string>>

// Functor<ValidatedTypeLambda<EitherTypeLambda, string>>.map: <A, B>(f: (a: A) => B) => <S, R, E, O>(self: Either<string, A>) => Either<string, B>
FunctorValidated.map

export interface Apply<F extends TypeLambda> extends Functor<F> {
  readonly ap: <S, R2, O2, E2, A>(
    fa: Kind<F, [S], [R2], [O2, E2, A]>
  ) => <R1, O1, E1, B>(
    self: Kind<F, [S], [R1], [O1, E1, (a: A) => B]>
  ) => Kind<F, [S], [R1 & R2], [O1 | O2, E1 | E2, B]>
}

Sep 27 '22 07:09 gcanti

I wonder if there have been any other efforts on this? I was aware of @mikearnaldi's excellent work in encoding HKT and was about to build a wrapper layer on top of fp-ts for a new project when I came across this work. Awesome stuff!

I took a stab at improving the API a little and came up with the following:


export interface HKT {
    readonly params?: unknown[]
    readonly type?: unknown
}

export type Kind<F extends HKT, Params extends unknown[]> = F extends { readonly type: unknown }
    ? (F & {
        readonly params: Params
    })["type"]
    : {
        readonly _F: F
        readonly _params: () => Params
    }

 export interface Functor<F extends HKT> {
    readonly map: <A, B>(
      f: (a: A) => B
    ) => (fa: Kind<F, [A]>) => Kind<F, [B]>
 }
 export interface Bifunctor<F extends HKT> {
    readonly bimap: <A, B, E, G>(
      f: (e: E) => G,
      g: (a: A) => B
    ) => (fae: Kind<F, [A, E]>) => Kind<F, [B, G]>
 }


export interface EitherHKT_C<E> extends HKT {
    readonly type: Either<E, this["params"][0]>
}
export interface EitherHKT extends HKT {
    readonly type: Either<this["params"][1], this["params"][0]>
}

const eitherFunctor = <E>(): Functor<EitherHKT_C<E>> => ({
  map: f => fa => isLeft(fa) ? fa : { ...fa, right: f(fa.right) }
})

const eitherBiFunctor = (): Bifunctor<EitherHKT> => ({
  bimap: (f, g) => fae =>  isLeft(fae) ? left(f(fae.left)) : right(g(fae.right))
})


const foo: Kind<EitherHKT_C<string>, [number]> = { _tag: "Left", left: "error"}
const bar: Kind<EitherHKT, [number, string]> = { _tag: "Right", right: 1}

There's some tradeoff here, like the order of the type args, that could be confusing. Or needing to wrap the functor instance in a function to keep E generic.

But at least, imo, this could be a somewhat cleaner API? more readable, no need to encode all possible args in the HKT type upfront. Haven't explored much more other than this simple PoC here tho. Quite possible that there'll be other problems but wondering if anyone's tried something similar?

Mar 05 '23 10:03 tiansivive

I wonder if there have been any other efforts on this? I was aware of @mikearnaldi's excellent work in encoding HKT and was about to build a wrapper layer on top of fp-ts for a new project when I came across this work. Awesome stuff!

I took a stab at improving the API a little and came up with the following:
export interface HKT {
    readonly params?: unknown[]
    readonly type?: unknown
}

export type Kind<F extends HKT, Params extends unknown[]> = F extends { readonly type: unknown }
    ? (F & {
        readonly params: Params
    })["type"]
    : {
        readonly _F: F
        readonly _params: () => Params
    }

 export interface Functor<F extends HKT> {
    readonly map: <A, B>(
      f: (a: A) => B
    ) => (fa: Kind<F, [A]>) => Kind<F, [B]>
 }
 export interface Bifunctor<F extends HKT> {
    readonly bimap: <A, B, E, G>(
      f: (e: E) => G,
      g: (a: A) => B
    ) => (fae: Kind<F, [A, E]>) => Kind<F, [B, G]>
 }


export interface EitherHKT_C<E> extends HKT {
    readonly type: Either<E, this["params"][0]>
}
export interface EitherHKT extends HKT {
    readonly type: Either<this["params"][1], this["params"][0]>
}

const eitherFunctor = <E>(): Functor<EitherHKT_C<E>> => ({
  map: f => fa => isLeft(fa) ? fa : { ...fa, right: f(fa.right) }
})

const eitherBiFunctor = (): Bifunctor<EitherHKT> => ({
  bimap: (f, g) => fae =>  isLeft(fae) ? left(f(fae.left)) : right(g(fae.right))
})


const foo: Kind<EitherHKT_C<string>, [number]> = { _tag: "Left", left: "error"}
const bar: Kind<EitherHKT, [number, string]> = { _tag: "Right", right: 1}
There's some tradeoff here, like the order of the type args, that could be confusing. Or needing to wrap the functor instance in a function to keep E generic.

But at least, imo, this could be a somewhat cleaner API? more readable, no need to encode all possible args in the HKT type upfront. Haven't explored much more other than this simple PoC here tho. Quite possible that there'll be other problems but wondering if anyone's tried something similar?

We tried multiple times, the result is "either you fix the set of params and their variance or you get to something that will break inference, and soundness, significantly".

Following is where we landed at the end: https://github.com/Effect-TS/data/blob/main/src/HKT.ts

Mar 05 '23 10:03 mikearnaldi

fp-ts
fp-ts copied to clipboard

Tuple-powered HKT encoding

🚀 Feature request

Current Behavior

Desired Behavior

Suggested Solution

Who does this impact? Who is this for?

Describe alternatives you've considered

fp-ts fp-ts copied to clipboard

Tuple-powered HKT encoding

🚀 Feature request

Current Behavior

Desired Behavior

Suggested Solution

Who does this impact? Who is this for?

Describe alternatives you've considered

fp-ts
fp-ts copied to clipboard