[RFC] Unified Kind and Typeclass encoding

raveclassic commented 4 years ago

🚀 Feature request

Current Behavior

At the moment we need to write a ton of overloading boilerplate for HKT-generic function:

import { Functor, Functor1, Functor2, Functor2C, Functor3, Functor4 } from 'fp-ts/lib/Functor';
import { HKT, Kind, Kind2, Kind3, Kind4, URIS, URIS2, URIS3, URIS4 } from 'fp-ts/lib/HKT';

export function mapTwice<F extends URIS4>(
    F: Functor4<F>,
): <S, R, E, A>(fa: Kind4<F, S, R, E, A>, f: (a: A) => A) => Kind4<F, S, R, E, A>;
export function mapTwice<F extends URIS3>(
    F: Functor3<F>,
): <R, E, A>(fa: Kind3<F, R, E, A>, f: (a: A) => A) => Kind3<F, R, E, A>;
export function mapTwice<F extends URIS2>(F: Functor2<F>): <E, A>(fa: Kind2<F, E, A>, f: (a: A) => A) => Kind2<F, E, A>;
export function mapTwice<F extends URIS2, E>(
    F: Functor2C<F, E>,
): <A>(fa: Kind2<F, E, A>, f: (a: A) => A) => Kind2<F, E, A>;
export function mapTwice<F extends URIS>(F: Functor1<F>): <A>(fa: Kind<F, A>, f: (a: A) => A) => Kind<F, A>;
export function mapTwice<F>(F: Functor<F>): <A>(fa: HKT<F, A>, f: (a: A) => A) => HKT<F, A>;
export function mapTwice<F>(F: Functor<F>): <A>(fa: HKT<F, A>, f: (a: A) => A) => HKT<F, A> {
    return (fa, f) => F.map(F.map(fa, f), f);
}

Evenmore the signature's missing overloads for missing Functor3C and Functor4C. And possibly overloads for other constrained functors, not only by the E type arg.

That's ugly.

Desired Behavior

We want a clean and concise solution for writing fully generic functions like:

export function mapTwice<F extends URIS>(
  F: Functor<F>
): <S, R, E, A>(fa: Kind<F, S, R, E, A>, f: (a: A) => A) => Kind<F, S, R, E, A> {
  return (fa, f) => F.map(F.map(fa, f), f)
}

Important thing is that we would also like to automate "currying" of typeclasses (no *C names).

Who does this impact? Who is this for?

All users of fp-ts especially library authors.

Describe alternatives you've considered

None

Additional context

Described approach means that there's a single dictionary left and a single version of a typeclass. There's no sensible profit in maintaining separate versions like HKT, Kind, Kind2, Monad, MonadC etc. It also means that a typeclass supports constrained arguments out of the box.

Your environment

Software	Version(s)
fp-ts	2.2.0
TypeScript	3.7.2

raveclassic commented 4 years ago

I've updated the solution and changed Auto to be branded with unique symbol instead of just extending Symbol. This allows support of Symbol type.

raveclassic commented 4 years ago

"Auto-currying" is not working, damn :(

interface Bifunctor<F extends URIS, FS = Auto, FR = Auto, FE = Auto> extends Functor<F, FS, FR, FE> {
  readonly mapLeft: <S, R, E, A, G>(
    fea: Kind<F, Or<FS, S>, Or<FR, R>, Or<FE, E>, A>,
    f: (e: E) => G
  ) => Kind<F, Or<FS, S>, Or<FR, R>, Or<FE, G>, A>
}

function getValidation<SE>(S: Semigroup<SE>): Bifunctor<'Either2', Auto, Auto, SE> {
  return {
    URI: 'Either2',
    map: functorEither.map,
    mapLeft: (fa, f) => {
      if (fa.tag === 'Left') {
        return { tag: 'Left', left: f(fa.left) }
        //                            ^-- fa.left is of type Or<SE, E> but needed just SE
      }
      return fa
    }
  }
}

qlonik commented 4 years ago

Hello. I was independently working on partially applied HKTs, but ended up with the thing which also is doing something similar to this issue and I wanted to share so that it does not get lost. If you have time, could you have a look and comment if it is broken or if it looks good?

Some not relevant code pieces

```typescript // from https://github.com/microsoft/TypeScript/issues/23689#issuecomment-512114782 export interface CompileError { readonly __compileError: never } export type NotAllowedHKT = CompileError<['Passed hkt is not allowed:', hkt]> export type UnmatchedURI = CompileError<[hkt, 'needs to be', S, 'passed', uri]> export type AnyType = unknown & { readonly _Any: unique symbol } export type HoleType = { readonly _Hole: unique symbol } ```

In this approach, I'm reusing HKT interfaces in order to attempt to approximate partially applied Kinds.

We can introduce apHKT1 which applies 1 given type to a given partially applied hkt. It should be failing when it is not able to apply some of the items. We can also add liftKind0 which lifts any existing URI string into corresponding HKT with zero passed partially bound types. We also can add resolveHKT0 which resolves HKT that we previously bound to types.

It appears that these three definitions should be enough for the following, but I added few more incomplete constructors, destructors and applications to simplify some operations in the code. The extra types are in these categories:

apHKTn - applies few arguments at the same time, instead of just one
liftKindn - lifts the kind and applies few given arguments right away
resolveHKTn - applies remaining types and resolves HKT into kind

//#region hkt
export type apHKT1<hkt, S> = hkt extends HKT4<infer URI, HoleType, infer R, infer E, infer A>
  ? HKT4<URI, S, R, E, A>
  : hkt extends HKT4<infer URI, infer S_, HoleType, infer E, infer A>
  ? HKT4<URI, S_, S, E, A>
  : hkt extends HKT4<infer URI, infer S_, infer R, HoleType, infer A>
  ? HKT4<URI, S_, R, S, A>
  : hkt extends HKT4<infer URI, infer S_, infer R, infer E, HoleType>
  ? HKT4<URI, S_, R, E, S>
  : hkt extends HKT3<infer URI, HoleType, infer E, infer A>
  ? HKT3<URI, S, E, A>
  : hkt extends HKT3<infer URI, infer R, HoleType, infer A>
  ? HKT3<URI, R, S, A>
  : hkt extends HKT3<infer URI, infer R, infer E, HoleType>
  ? HKT3<URI, R, E, S>
  : hkt extends HKT2<infer URI, HoleType, infer A>
  ? HKT2<URI, S, A>
  : hkt extends HKT2<infer URI, infer E, HoleType>
  ? HKT2<URI, E, S>
  : hkt extends HKT<infer URI, HoleType>
  ? HKT<URI, S>
  : NotAllowedHKT<hkt>

export type liftKind0<uri> = uri extends URIS4
  ? HKT4<uri, HoleType, HoleType, HoleType, HoleType>
  : uri extends URIS3
  ? HKT3<uri, HoleType, HoleType, HoleType>
  : uri extends URIS2
  ? HKT2<uri, HoleType, HoleType>
  : uri extends URIS
  ? HKT<uri, HoleType>
  : NotAllowedHKT<uri>

export type resolveHKT0<hkt> = hkt extends HKT4<infer URI, infer S, infer R, infer E, infer A>
  ? URI extends URIS4
    ? Kind4<URI, S, R, E, A>
    : UnmatchedURI<hkt, 'URIS4', URI>
  : hkt extends HKT3<infer URI, infer R, infer E, infer A>
  ? URI extends URIS3
    ? Kind3<URI, R, E, A>
    : UnmatchedURI<hkt, 'URIS3', URI>
  : hkt extends HKT2<infer URI, infer E, infer A>
  ? URI extends URIS2
    ? Kind2<URI, E, A>
    : UnmatchedURI<hkt, 'URIS2', URI>
  : hkt extends HKT<infer URI, infer A>
  ? URI extends URIS
    ? Kind<URI, A>
    : UnmatchedURI<hkt, 'URIS', URI>
  : NotAllowedHKT<hkt>
//#endregion

Helpers types

```typescript //#region extra-helpers export type apHKT2 = hkt extends HKT4 ? HKT4 : hkt extends HKT3 ? HKT3 : hkt extends HKT2 ? HKT2 : NotAllowedHKT export type apHKT3 = hkt extends HKT4 ? HKT4 : hkt extends HKT3 ? HKT3 : NotAllowedHKT export type apHKT4 = hkt extends HKT4 ? HKT4 : NotAllowedHKT export type liftKind1 = uri extends URIS4 ? HKT4 : uri extends URIS3 ? HKT3 : uri extends URIS2 ? HKT2 : uri extends URIS ? HKT : NotAllowedHKT export type liftKind2 = uri extends URIS4 ? HKT4 : uri extends URIS3 ? HKT3 : uri extends URIS2 ? HKT2 : NotAllowedHKT export type liftKind3 = uri extends URIS4 ? HKT4 : uri extends URIS3 ? HKT3 : NotAllowedHKT export type liftKind4 = uri extends URIS4 ? HKT4 : NotAllowedHKT export type resolveHKT1 = hkt extends HKT4 ? URI extends URIS4 ? Kind4 : UnmatchedURI : hkt extends HKT3 ? URI extends URIS3 ? Kind3 : UnmatchedURI : hkt extends HKT2 ? URI extends URIS2 ? Kind2 : UnmatchedURI : hkt extends HKT ? URI extends URIS ? Kind : UnmatchedURI : NotAllowedHKT export type resolveHKT2 = hkt extends HKT4 ? URI extends URIS4 ? Kind4 : UnmatchedURI : hkt extends HKT3 ? URI extends URIS3 ? Kind3 : UnmatchedURI : hkt extends HKT2 ? URI extends URIS2 ? Kind2 : UnmatchedURI : NotAllowedHKT export type resolveHKT3 = hkt extends HKT4 ? URI extends URIS4 ? Kind4 : UnmatchedURI : hkt extends HKT3 ? URI extends URIS3 ? Kind3 : UnmatchedURI : NotAllowedHKT export type resolveHKT4 = hkt extends HKT4 ? URI extends URIS4 ? Kind4 : UnmatchedURI : NotAllowedHKT //#endregion ``` Here is example how helpers do the same thing as base types, just with less code ```typescript //#region helpers test type X = apHKT1, A>, B> type RX = resolveHKT0> type Y = liftKind2<'Either', A, B> type RY = resolveHKT0> type Z = apHKT1, B> type Test1 = Y extends X ? X extends Y ? 'good' : 'second comparison' : 'first comparison' type Test2 = Y extends Z ? Z extends Y ? 'good' : 'second comparison' : 'first comparison' type Test3 = RY extends RX ? RX extends RY ? 'good' : 'second comparison' : 'first comparison' type Test4 = resolveHKT2, A, B> extends Kind2<'Either', A, B> ? Kind2<'Either', A, B> extends resolveHKT2, A, B> ? 'good' : 'second comparison' : 'first comparison' declare const typeTest1: Test1 declare const typeTest2: Test2 declare const typeTest3: Test3 declare const typeTest4: Test4 //#endregion ```

We can now implement getFunctorEither and getValidationEither. The implementation of both of these seem to be type checking. Unfortunately, there is a need to explicitly pass generic parameter E. Maybe there is an improvement that can be done here?

//#region abstract
interface Functor<F> {
  readonly map: <A, B>(fa: resolveHKT1<F, A>, f: (a: A) => B) => resolveHKT1<F, B>
}
interface Bifunctor<F, E> extends Functor<apHKT1<F, E>> {
  readonly mapLeft: <A, G>(fa: resolveHKT2<F, E, A>, f: (e: E) => G) => resolveHKT2<F, G, A>
}
//#endregion

//#region adt
function getFunctorEither<E = never>(): Functor<liftKind1<'Either', E>> {
  return {
    map: (fa, f) => (isLeft(fa) ? fa : right(f(fa.right))),
  }
}
function getValidationEither<E = never>(S: Semigroup<E>): Bifunctor<liftKind0<'Either'>, E> {
  return {
    ...getFunctorEither<E>(),
    mapLeft: (fa, f) => (isLeft(fa) ? left(f(fa.left)) : fa),
  }
}
//#endregion

//#region test
const mapTwice = <F>(F: Functor<F>) => <A>(fa: resolveHKT1<F, A>, f: (a: A) => A): resolveHKT1<F, A> =>
  F.map(F.map(fa, f), f)

const f = (n: string): string => n.toUpperCase()
const test1 = mapTwice(getFunctorEither<number>())(left(1), f) // Ok - Either<string, string>
const test2 = mapTwice(getFunctorEither<number>())(left(1), f) // Ok - Either<number, string>
const v: Functor<liftKind1<'Either', string>> = getValidationEither(semigroupString)
const test3 = mapTwice(v)(left('34'), f) // Ok - Either<string, string>
const test4 = mapTwice(v)(left(34), f) // Error - number is not assignable to string
const test5 = mapTwice(getFunctorEither<symbol>())(left(Symbol()), () => '123') // Ok - Either<symbol, string>
const test6 = mapTwice<liftKind1<'Either', string>>(getValidationEither(semigroupString))(left('34'), f) // Ok - Either<string, string>

const semigroupSymbol: Semigroup<symbol> = {
  concat: (x, y) => Symbol('concat'),
}
const validationSymbol = getValidationEither(semigroupSymbol)
const test7 = validationSymbol.map(left(Symbol()), f) // Ok - Either<Symbol, string>
const test8 = validationSymbol.map(left('foo'), f) // Error - string is not assignable to Symbol
const test9 = mapTwice<liftKind1<'Either', symbol>>(validationSymbol)(left(Symbol()), f) // Ok - Either<Symbol, string>
const test10 = mapTwice<liftKind1<'Either', symbol>>(validationSymbol)(left('foo'), f) // Error - string is not assignable to Symbol
//#endregion

Also, from tests, I discovered that Typescript does not want to reduce the type Functor<apHKT1<liftKind0<'Either'>, string>> to Functor<liftKind1<'Either', string>>.

That is weird, since it seem to be able to reduce those types in other places and verify that they are same:

type X = Functor<liftKind1<'Either', string>>
type Y = Functor<apHKT1<liftKind0<'Either'>, string>>
declare let x: X
declare let y: Y
y = x
x = y

This issue causes that awkward functor signature in few places when calling mapTwice. Maybe this can be improved as well somehow?

gcanti / fp-ts