How HKT really works in fp-ts?

Question

Check out the code below. I also added that to this link from typescript playground. I gathered parts of the fp-ts in one place to test and understand how HKT works and simulated there.

type Identity<A> = { _tag: 'Identity', a: A }

// --------------------

type Option<A> = Some<A> | None

interface Some<A> {
  _tag: 'Some'
  value: A
}

interface None {
  _tag: 'None'
}

const some = <A,>(x: A): Option<A> => 
  ({ _tag: 'Some', value: x })

const none: Option<never> = 
  { _tag: 'None' }

const isNone = <A,>(x: Option<A>): x is None => 
  x._tag === 'None'

// --------------------

type Either<E, A> = Left<E> | Right<A>

interface Left<E> {
  _tag: 'Left'
  left: E
}

interface Right<A> {
  _tag: 'Right'
  right: A
}

const left = <E,A=never>(x: E):  Either<E, A> => ({ _tag: 'Left', left: x})
const right = <A,E=never>(x: A):  Either<E, A> => ({ _tag: 'Right', right: x})

const isLeft = <E, A>(a: Either<E, A>): a is Left<E> => 
  a._tag === 'Left'


// --------------------

interface URItoKind1<A> {
    'Identity': Identity<A>
    'Option': Option<A>
}

interface URItoKind2<E,A> {
    'Either': Either<E,A>
}

type URIS1 = keyof URItoKind1<any>
type URIS2 = keyof URItoKind2<any, any>

type Kind1<URI extends URIS1, A> = URItoKind1<A>[URI]
type Kind2<URI extends URIS2, E, A> = URItoKind2<E,A>[URI]

// type HKT1<URI, A> = { URI: URI; a: A };              // FROM FP-TS
type HKT1<URI, A> = { What: string }                    // HERE IS CONFUSING TO ME. THIS COMPILES
// type HKT2<URI, A, B> = { URI: URI; a: A; b: B };     // FROM FP-TS
type HKT2<URI, A, B> = { Hello: number }                // HERE IS CONFUSING TO ME. THIS COMPILES

interface Functor1<F extends URIS1> {
    map: <A, B>(fa: Kind1<F, A>, f: (a: A) => B) => Kind1<F, B>
}

interface Functor2<F extends URIS2> {
    map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}

interface Functor<F> {
    map: <A, B>(fa: HKT1<F, A>, f: (a: A) => B) => HKT1<F, B>
}

// --------------------------

const optionFunctor: Functor1<'Option'> = {
  map: <A,B>(fa: Option<A>, f: (x: A) => B): Option<B> => 
    isNone(fa) ? none : some(f(fa.value))
}

const eitherFunctor: Functor2<'Either'> = {
  map: <E,A,B>(fa: Either<E, A>, f: (x: A) => B): Either<E, B> => 
    isLeft(fa) ? fa : right(f(fa.right))
}

// ---------------------------

function lift<F extends URIS2>(F: Functor2<F>): <A, B>(f: (a: A) => B) => <E>(fa: Kind2<F, E, A>) => Kind2<F, E, B>
function lift<F extends URIS1>(F: Functor1<F>): <A, B>(f: (a: A) => B) => (fa: Kind1<F, A>) => Kind1<F, B>
function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT1<F, A>) => HKT1<F, B>       // IF YOU COMMENT THIS TYPESCRIPT WILL NOT BE HAPPY, BUT WHY IT WORKS IN THE FIRST PLACE!
{
  return (f) => (fa) => F.map(fa, f)
}

const liftOption = lift(optionFunctor)
const liftEither = lift(eitherFunctor)

const increment = (x: number) => x+1

console.log(liftOption(increment)(some(12)))
console.log(liftEither(increment)(right(12)))

This compiles ok, and runs ok.

I change the HKT1 and HKT2 to something totally nonsense from

type HKT1<URI, A> = { URI: URI; a: A };
type HKT2<URI, A, B> = { URI: URI; a: A; b: B };

to

type HKT1<URI, A> = { What: string }
type HKT2<URI, A, B> = { Hello: number }

But the code compiles ok. Why?

The more strange part is if we comment the line...

function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT1<F, A>) => HKT1<F, B>

...which is an overload and the default case. the code stops compiling!

How does HKT works here? How the types HKT1 is glueing Functor1 and Functor2 together under Functor?

Answer 1

Let's go one by one:

---

1. how Functor matches the types to Functor1, Functor2, ... at the TypeScript level.

You have a Function Overload with 2 Overload Signatures and one Implementation Signature:

function lift<F extends URIS2>(F: Functor2<F>): <A, B>(f: (a: A) => B) => <E>(fa: Kind2<F, E, A>) => Kind2<F, E, B>
function lift<F extends URIS1>(F: Functor1<F>): <A, B>(f: (a: A) => B) => (fa: Kind1<F, A>) => Kind1<F, B>
function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT1<F, A>) => HKT1<F, B> 

When you use lift with optionFunctor:

const liftOption = lift(optionFunctor)
//                  ^? function lift<"Option">(F: Functor1<"Option">): <A, B>(f: (a: A) => B) => (fa: Option<A>) => Option<B>

you use second overload signature with Functor1 because optionFunctor is Functor1

When you use lift with eitherFunctor:

const liftEither = lift(eitherFunctor)
//                  ^? function lift<"Either">(F: Functor2<"Either">): <A, B>(f: (a: A) => B) => <E>(fa: Either<E, A>) => Either<E, B>

you use first overload signature with Functor2 because eitherFunctor is Functor2

TS Playground with comments I've added - https://tsplay.dev/WYylvW

---

2. With the lift function overload, I can't explain why commenting the last overload (the one with Functor and HKT) creates an error for other overloads.

Function overload should have Implementation Signature so each overload would narrow down from it (which comes last).

But you need to also bear in mind that your HKT1 is connected to Functor:

type HKT1<URI, A> = { What: string }

interface Functor<F> {
    map: <A, B>(fa: HKT1<F, A>, f: (a: A) => B) => HKT1<F, B>
}

So as you don't have any Generic Constraints in <F>:

function lift<F>(F: Functor<F>): <A, B>(f: (a: A) => B) => (fa: HKT1<F, A>) => HKT1<F, B>

It's still correct TypeScript code, even though it maps to something that you don't expect.

Although, when you comment it out, you start getting type errors, such as Argument of type 'Functor1<"Option">' is not assignable to parameter of type 'Functor2<"Either">'

The important bit here is that "The implementation signature must also be compatible with the overload signatures". When you remove the implementation signature and make second overload the implementation signature, it breaks this rule so that fa function in map doesn't have a common denominator anymore (it was a HKT1<F, A>).

You can prove it by removing HKT1, Functor and just put this instead as generic overload, type error goes away:

function lift<F>(F: { map: <A, B>(fa: {}, f: (a: A) => B) => {}}): <A, B>(f: (a: A) => B) => (fa: {}) => {}

TypeScript Playground with my changes - https://tsplay.dev/NaZREm

---

3. Why changing HKT1 type definition to some random object type does not lead to compile error.

There are no Generic Constraints at implementation signature (the one with Functor and HKT1) so you won't get type error

The signature of the implementation is not visible from the outside. When writing an overloaded function, you should always have two or more signatures above the implementation of the function.

---

Please let me know if you have any other questions, happy to explain them