Simple HKT for simple Functor

[dagda1]

Sadly for me, this level of typescript is over my head.

I am trying to understand functional programming and currently functor and got bitten by the lack of higher kinded types.

I would have have like to have done this:

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

Currently I have this definition:

export interface Functor<
  FA extends Object | Array<A>, A, FB extends Object | Array<B>, B
> {
  map: (f: (a: A) => B, fa: FA) => FB;
}

And an implementation would look like:

export const getArrayFunctor = <A, B>(): Functor<A[], A, B[], B> => {
  return {
    map: (fn, fa) => {
      return fa.map(fn);
    }
  };
};

If possible, could you give me any pointers as to how I could create an HKT that would fit the f a and f b in a functor type?

[SimonMeskens]

Hey @dagda1

Yeah, the current examples are at a very high level (I struggle with it myself, but I had help), to showcase what the library is capable of, but luckily it is super simple to work with at a lower level.

Currently the library itself is still a bit hard to use and understand for simpler examples like yours (the shape of your functor is uncurried, and you're using it in a concrete manner, which simplifies things a lot), but luckily, @adameu wrote a nice example of a TypeProps-esque library for just such types.

Here's the exampel%3A%20Generic%3CF%2C%20B%3E%3B%0D%0A%7D%0D%0A%0D%0Ainterface%20Monad%3CF%20extends%20RegisteredTypes%2C%20A%3E%20extends%20Functor%3CF%2C%20A%3E%20%7B%0D%0A%20%20chain%3CB%3E(f%3A%20(_%3A%20A)%20%3D%3E%20Generic%3CF%2C%20B%3E)%3A%20Generic%3CF%2C%20B%3E%3B%0D%0A%7D%0D%0A%0D%0A%2F%20Identity%20%2F%0D%0Aclass%20Identity%3CA%20%3D%20any%3E%20implements%20Monad%3CIdentity%2C%20A%3E%20%7B%0D%0A%20%20constructor(private%20readonly%20value%3A%20A)%20%7B%7D%0D%0A%0D%0A%20%20chain%3CB%3E(f%3A%20(%3A%20A)%20%3D%3E%20Identity%3CB%3E)%3A%20Identity%3CB%3E%20%7B%0D%0A%20%20%20%20return%20f(this.value)%3B%0D%0A%20%20%7D%0D%0A%20%20fold%3CB%3E(f%3A%20(%3A%20A)%20%3D%3E%20B)%3A%20B%20%7B%0D%0A%20%20%20%20return%20f(this.value)%3B%0D%0A%20%20%7D%0D%0A%20%20map%3CB%3E(f%3A%20(%3A%20A)%20%3D%3E%20B)%3A%20Identity%3CB%3E%20%7B%0D%0A%20%20%20%20return%20new%20Identity(f(this.value))%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0Aconst%20identity%20%3D%20%3CA%3E(a%3A%20A)%3A%20Identity%3CA%3E%20%3D%3E%20new%20Identity(a)%3B%0D%0A%0D%0Ainterface%20TypesDictionary%3CF%2C%20A%20%3D%20never%3E%20%7B%0D%0A%20%20Identity%3A%20%7B%0D%0A%20%20%20%20param%3A%20F%20extends%20Identity%3Cinfer%20A%3E%20%3F%20A%20%3A%20never%3B%0D%0A%20%20%20%20type%3A%20F%20extends%20Identity%20%3F%20Identity%3CA%3E%20%3A%20never%3B%0D%0A%20%20%7D%3B%0D%0A%7D%0D%0A%0D%0A%2F%20Maybe%20%2F%0D%0Aabstract%20class%20Maybe%3CA%20%3D%20any%3E%20implements%20Monad%3CMaybe%2C%20A%3E%20%7B%0D%0A%20%20abstract%20maybe%3CB%3E(b%3A%20B%2C%20f%3A%20(%3A%20A)%20%3D%3E%20B)%3A%20B%3B%0D%0A%20%20chain%3CB%3E(f%3A%20(%3A%20A)%20%3D%3E%20Maybe%3CB%3E)%3A%20Maybe%3CB%3E%20%7B%0D%0A%20%20%20%20return%20this.maybe(nothing%2C%20f)%3B%0D%0A%20%20%7D%0D%0A%20%20map%3CB%3E(f%3A%20(%3A%20A)%20%3D%3E%20B)%3A%20Maybe%3CB%3E%20%7B%0D%0A%20%20%20%20return%20this.maybe(nothing%2C%20x%20%3D%3E%20just(f(x)))%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0A%0D%0Aclass%20Just%3CA%3E%20extends%20Maybe%3CA%3E%20%7B%0D%0A%20%20constructor(private%20readonly%20value%3A%20A)%20%7B%0D%0A%20%20%20%20super()%3B%0D%0A%20%20%7D%0D%0A%20%20maybe(%2C%20f)%20%7B%0D%0A%20%20%20%20return%20f(this.value)%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0Aconst%20just%20%3D%20%3CA%3E(a%3A%20A)%3A%20Maybe%3CA%3E%20%3D%3E%20new%20Just(a)%3B%0D%0A%0D%0Aclass%20Nothing%20extends%20Maybe%3Cnever%3E%20%7B%0D%0A%20%20maybe(b)%20%7B%0D%0A%20%20%20%20return%20b%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0Aconst%20nothing%3A%20Maybe%3Cnever%3E%20%3D%20new%20Nothing()%3B%0D%0A%0D%0Ainterface%20TypesDictionary%3CF%2C%20A%20%3D%20never%3E%20%7B%0D%0A%20%20Maybe%3A%20%7B%0D%0A%20%20%20%20param%3A%20F%20extends%20Maybe%3Cinfer%20A%3E%20%3F%20A%20%3A%20never%3B%0D%0A%20%20%20%20type%3A%20F%20extends%20Maybe%20%3F%20Maybe%3CA%3E%20%3A%20never%3B%0D%0A%20%20%7D%3B%0D%0A%7D%0D%0A%0D%0A%2F%20Either%20%2F%0D%0Aabstract%20class%20Either%3CL%20%3D%20any%2C%20R%20%3D%20any%3E%20implements%20Monad%3CEither%3CL%3E%2C%20R%3E%20%7B%0D%0A%20%20abstract%20either%3CB%3E(f%3A%20(%3A%20L)%20%3D%3E%20B%2C%20g%3A%20(%3A%20R)%20%3D%3E%20B)%3A%20B%3B%0D%0A%0D%0A%20%20chain%3CB%3E(f%3A%20(%3A%20R)%20%3D%3E%20Either%3CL%2C%20B%3E)%3A%20Either%3CL%2C%20B%3E%20%7B%0D%0A%20%20%20%20return%20this.either(left%2C%20f)%3B%0D%0A%20%20%7D%0D%0A%20%20map%3CB%3E(f%3A%20(_%3A%20R)%20%3D%3E%20B)%3A%20Either%3CL%2C%20B%3E%20%7B%0D%0A%20%20%20%20return%20this.either%3CEither%3CL%2C%20B%3E%3E(left%2C%20x%20%3D%3E%20right(f(x)))%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0A%0D%0Aclass%20Left%3CA%3E%20extends%20Either%3CA%2C%20never%3E%20%7B%0D%0A%20%20constructor(private%20readonly%20_value%3A%20A)%20%7B%0D%0A%20%20%20%20super()%3B%0D%0A%20%20%7D%0D%0A%20%20either(f)%20%7B%0D%0A%20%20%20%20return%20f(this._value)%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0Aconst%20left%20%3D%20%3CA%3E(a%3A%20A)%3A%20Either%3CA%2C%20never%3E%20%3D%3E%20new%20Left(a)%3B%0D%0A%0D%0Aclass%20Right%3CA%3E%20extends%20Either%3Cnever%2C%20A%3E%20%7B%0D%0A%20%20constructor(private%20readonly%20value%3A%20A)%20%7B%0D%0A%20%20%20%20super()%3B%0D%0A%20%20%7D%0D%0A%20%20either(%2C%20g)%20%7B%0D%0A%20%20%20%20return%20g(this.value)%3B%0D%0A%20%20%7D%0D%0A%7D%0D%0Aconst%20right%20%3D%20%3CA%3E(a%3A%20A)%3A%20Either%3Cnever%2C%20A%3E%20%3D%3E%20new%20Right(a)%3B%0D%0A%0D%0Ainterface%20TypesDictionary%3CF%2C%20A%20%3D%20never%3E%20%7B%0D%0A%20%20Either%3A%20%7B%0D%0A%20%20%20%20param%3A%20F%20extends%20Either%3Cany%2C%20infer%20R%3E%20%3F%20R%20%3A%20never%3B%0D%0A%20%20%20%20type%3A%20F%20extends%20Either%3Cinfer%20L%3E%20%3F%20Either%3CL%2C%20A%3E%20%3A%20never%3B%0D%0A%20%20%7D%3B%0D%0A%7D%0D%0A%0D%0A%2F%20Static%20methods%20%2F%0D%0Aconst%20chain%20%3D%20%3C%0D%0A%20%20F%20extends%20RegisteredTypes%20%26%20Monad%3CF%2C%20A%3E%2C%0D%0A%20%20A%20extends%20TypeParamOf%3CF%3E%2C%0D%0A%20%20B%0D%0A%3E(%0D%0A%20%20f%3A%20(%3A%20A)%20%3D%3E%20Monad%3CF%2C%20B%3E%2C%0D%0A%20%20fa%3A%20F%0D%0A)%3A%20Generic%3CF%2C%20B%3E%20%3D%3E%20fa.chain(f%20as%20any)%3B%0D%0Aconst%20map%20%3D%20%3C%0D%0A%20%20F%20extends%20RegisteredTypes%20%26%20Functor%3CF%2C%20A%3E%2C%0D%0A%20%20A%20extends%20TypeParamOf%3CF%3E%2C%0D%0A%20%20B%0D%0A%3E(%0D%0A%20%20f%3A%20(_%3A%20A)%20%3D%3E%20B%2C%0D%0A%20%20fa%3A%20F%0D%0A)%3A%20Generic%3CF%2C%20B%3E%20%3D%3E%20fa.map(f)%3B%0D%0A%0D%0A%2F%20Examples%20%2F%0D%0Aconst%20x%20%3D%20right(%22Hello%20World%22)%20as%20Either%3Cnumber%2C%20string%3E%3B%0D%0Aconst%20y%20%3D%20map(val%20%3D%3E%20val.length%2C%20x)%3B%0D%0Aconst%20z%20%3D%20chain(val%20%3D%3E%20(val%20%3C%205%20%3F%20right(val)%20%3A%20left(val))%2C%20y)%3B%0D%0A)

I suggest you look at that one for now and see if you can understand that example (feel free to ask us questions). I'll work on supporting your example ASAP in the library proper.

[dagda1]

Hi @SimonMeskens thank you for your response.

This is still a bit confusing and I would like to ask the following questions.

First of all:

interface TypesDictionary<F, A = never> {
  never: { param: never; type: never };
}

TypesDictionary takes 2 generic parameters that are never used and then specifies a never structure with param and type which are also never. So my understanding of never is that it forces the developer to always specify a type and not default to {}. Please correct me if I am wrong.

type RegisteredTypes = TypesDictionary<any, any>[keyof TypesDictionary<
  any
  >]["type"];

I don't really understand this, I think it is saying that RegisteredTypes are a value of TypesDictionay but I've never seen a type with a string indexer like this and would really appreciate knowing what this is doing.

type Generic<F extends RegisteredTypes, A> = TypesDictionary<
  F,
  A
>[keyof TypesDictionary<F>]["type"];

I am guessing this is the HKT with F being my functor or structure and A being the concrete type but when I look at the functor interface:

interface Functor<F extends RegisteredTypes, A> {
  map<B>(f: (_: A) => B): Generic<F, B>;
}

I don't really get the difference between RegisteredTypes and Generic and why we need both.

Thank you again for the response and apologies for the questions but I would really love to understand this because I think my typescript knowledge would rocket.

[dagda1]

I also notice that this does not compile:

const map = <
  F extends RegisteredTypes & Functor<F, A>,
  A extends TypeParamOf<F>,
  B
>(
  f: (_: A) => B,
  fa: F
): Generic<F, B> => fa.map(f, fa);

It has the following errors;

Type 'any' is not assignable to type 'never'. Property 'map' does not exist on type 'F'.

The last one is surprising because F has a generic constraint on functor.

[SimonMeskens]

Oh boy, you're asking me to explain how it works, this is going to be fun :)

I'm writing up an explanation, give me some time, shouldn't be long

[dagda1]

take your time, you are being most helpful. whenever you have time

[SimonMeskens]

First off, the playground doesn't show any compilation errors for me, so I'm not sure, but I think you removed some code that makes it work or something like that. I'll use the names from that example (which is based on an older version of the library), the library uses slightly different names and it's debatable which ones are best (I go back and forth).

Okay, so TypesDictionary stores what I call "TypeProps". Basically, a TypeProp should be able to do two things:

• infer generic parameters
• construct a type when given generic parameters

The reason that TypesDictionary has two parameters it doesn't use, is because you are supposed to merge in TypeProps. Here's the example Identity TypeProp from the example:

interface TypesDictionary<F, A = never> {
  Identity: {
    param: F extends Identity<infer A> ? A : never;
    type: F extends Identity ? Identity<A> : never;
  };
}

param is a type that when given an F, gives you the parameter type. type is a similar type, that gives you the HKT when supplied with parameters. I use a slightly different type of TypeProp (I haven't decided yet what the best TypeProp looks like), but here's what an array TypeProp would look like in the example:

interface TypesDictionary<F, A = never> {
  Array: {
    param: F extends Array<infer A> ? A : never;
    type: F extends Array<any> ? Array<A> : never;
  };
}

Basically: param: if F is an array of A, I give you A type: if F is an array, I give you an array of A

Through declaration merging, all these types are merged together into one interface that we can now ask questions about registered types. That brings us to RegisteredTypes:

type RegisteredTypes = TypesDictionary<any, any>[keyof TypesDictionary<
  any
>]["type"];

Let's examine what this does. It uses mapped types to index into the TypesDictionary. Since it indexes it with [keyof TypesDictionary<any>], we get back all of the TypeProps in a union, like: TypeProp1 | TypeProp2. It then indexes them again, asking for their type property. Here's a toy example to show the concept:

interface Foo {
    baz: { type: number };
}

// This is merged in, so it could potentially be in another file even
interface Foo {
    bar: { type: string };
}

type FooProps = Foo[keyof Foo]; // FooProps = { type: number; } | { type: string; }
type FooTypes = Foo[keyof Foo]["type"]; // FooTypes = string | number

Now, since RegisteredTypes gave the TypesDictionary parameters any, any, all of the T extends Foo checks will return true and the parameter will be set to any. This means for the above two TypeProps, that the result of RegisteredTypes would be: Identity<any> | Array<any>. We can now use this type to check if some other type is a registered HKT.

Now, Generic<F, A> is indeed a type that means "HKT of F, with parameter A", or in your syntax F<A>. If you understood how RegisteredTypes work, it works almost the same, but instead of asking for every type with any, it provides a specific type and parameter. Generic<Array<any>, number would return Array<number>. Now this type check doesn't check for the input parameter, so you can also "map" types, meaning Generic<Array<number>, string> returns Array<string> too.

This means you correctly identified we don't need both RegisteredTypes and Generic, we could've just used Generic<any, any> instead of RegisteredTypes. It's just a simple alias, which is unnecessary.

Now, all of this finally leads to the ADT interfaces like Functor. Here's our definition:

interface Functor<F extends RegisteredTypes, A> {
  map<B>(f: (_: A) => B): Generic<F, B>;
}

I think it's fairly clear at this point what this does. If we rewrite it using the original syntax you used (and make the this explicit, to make it more clear what's going on), we get this:

interface Functor<F extends any<A> {
  map<B>(this: F<A>, f: (_: A) => B): F<B>;
}

Feel free to ask more questions, I will eventually need to write a document explaining how my library works and questions like yours are invaluable.

[SimonMeskens]

Alright, this is the latest and greatest contained functor sample. I'm very proud of the new system.

type unknown = {} | null | undefined;

// Functor
interface StaticFunctor<G> {
    map<F extends Generic<G>, U>(
        transform: (a: Parameters<F>[0]) => U,
        mappable: F
    ): Generic<F, [U]>;
}

// Examples
const arrayFunctor: StaticFunctor<any[]> = {
    map: <A, B>(fn: (a: A) => B, fa: A[]): B[] => {
        return fa.map(fn);
    }
};
const objectFunctor: StaticFunctor<object> = {
    map: <A, B>(fn: (a: A) => B, fa: A): B => {
        return fn(fa);
    }
};
const nullableFunctor: StaticFunctor<object | null | undefined> = {
    map: <A, B>(
        fn: (a: A) => B,
        fa: A | null | undefined
    ): B | null | undefined => {
        return fa != undefined ? fn(fa) : fa;
    }
};

const doubler = (x: number) => x * 2;

const xs = arrayFunctor.map(doubler, [4, 2]); // xs: number[]
const x = objectFunctor.map(doubler, 42); // x: number
const xNull = nullableFunctor.map(doubler, null); // xNull: null
const xSome = nullableFunctor.map(doubler, 4 as number | undefined); // xSome: number | undefined

const functor: StaticFunctor<unknown | any[]> = {
    map(fn, fa) {
        return Array.isArray(fa)
            ? arrayFunctor.map(fn, fa)
            : fa != undefined
                ? objectFunctor.map(fn, fa)
                : nullableFunctor.map(fn, fa);
    }
};

const ys = functor.map(doubler, [4, 2]); // ys: number[]
const y = functor.map(doubler, 42); // y: number
const yNull = functor.map(doubler, null); // yNull: null
const ySome = functor.map(doubler, 42 as number | undefined); // ySome: number | undefined

// Plumbing
interface TypeProps<T = {}, Params extends ArrayLike<any> = never> {
    array: {
        infer: T extends Array<infer A> ? [A] : never;
        construct: Params[0][];
    };
    null: {
        infer: null extends T ? [never] : never;
        construct: null;
    };
    undefined: {
        infer: undefined extends T ? [never] : never;
        construct: undefined;
    };
    unfound: {
        infer: [NonNullable<T>];
        construct: Params[0];
    };
}

type Match<T> = T extends infer U
    ? ({} extends U ? any
        : TypeProps<U>[Exclude<keyof TypeProps, "unfound">]["infer"]) extends never
    ? "unfound"
    : {
        [Key in Exclude<keyof TypeProps, "unfound">]:
        TypeProps<T>[Key]["infer"] extends never
        ? never : Key
    }[Exclude<keyof TypeProps, "unfound">] : never;

type Parameters<T> = TypeProps<T>[Match<T>]["infer"];

type Generic<
    T,
    Params extends ArrayLike<any> = ArrayLike<any>,
    > = TypeProps<T, Params>[Match<T>]["construct"];

[SimonMeskens]

Closing this one down for bookkeeping as it's resolved, you know where to find me to ask more questions :) (in here is fine too)