Monads over multiple parameters

[SimonMeskens]

@nadameu

TypeProp-esque Monad example

Okay, so I was thinking about your example code and how Haskell handles monads over types with multiple parameters and I think the solution is to use a little bit of your method and mine.

A TypeProp is an object that has a way to get a list of parameters and a way to construct a type, given parameters. This might change in the future, I have a few ideas in the pipeline that might define TypeProps differently. One thing is that this library is basically a dynamic, type-level pattern matcher. There's currently some TypeScript issues blocking it from allowing me to expose that behavior, but that might change things.

Now, here's how Haskell defines the Either monad:

instance Monad (Either e) where
    Left  l >>= _ = Left l
    Right r >>= k = k r

As you can see, it basically it creates a new TypeProp specifically for Monads, telling it how to infer parameters, like your example does. So now I'm thinking that the Monad interface's parameter shouldn't be a type, but a TypeProp. So far, so good, what's missing is a way to transform TypeProps, that is, you should be able to create a TypeProp from another TypeProp, telling it which parameters to infer and which ones to fill in.

I'll be working on this next. Thoughts?

[nadameu]

Haskell's implementation was exactly my inspiration for the code I shared.

I will give some thought into how to implement your idea for the next iteration of the library.

[SimonMeskens]

Yeah, your example and looking at Haskell's libraries gave me the right idea. I think I know how to do it too. I've already changed the TypeProps library to be a lot better thanks to your idea. I'll share my results hopefully tonight.

[SimonMeskens]

The problem with storing a TypeProp anywhere is that I'm currently blocked by a few restrictions in TypeScript, making it so only the global type dictionary works. The issue is this:

<T extends any>() => {
    infer: T extends Array<infer U> ? [U] : never
    construct: Array<T[0]>
}

This is a dynamic TypeProp, but there's no way to infer the return type right now. I can sidestep the issue, but until we get some way in the language to infer generic function types, that construct will never work. It's this same construct that I could use to generalize TypeProps to a full-blown pattern matcher.

[nadameu]

I don't know if this is exactly what you're looking for:

Setup

Let's create a few placeholders.

const _A = Symbol('placehoderA');
const _B = Symbol('placehoderB');
type _A = typeof _A;
type _B = typeof _B;

We can use these placeholders to represent a parameter that might vary.

For instance:

interface Bifunctor<F extends RegisteredTypes, A, B> {
  bimap<C, D>(f: (_: A) => C, g: (_:B) => D): Generic<F, C, D>;
}

class Either<L, R> implements Bifunctor<Either<_A, _B>, L, R> { ... }

Most of the time there will only be one variable parameter.

So let's create a shorthand representation.

type _ = _A;

Now let's use it:

class Either<L, R> implements Monad<Either<L, _>, R> { ... }

In Haskell this would be:

instance Monad (Either e) where ...

The rest of the code is almost the same as before.

Some changes made:
type is to create the RegisteredTypes set.
params is to extract the params from a given instance.
construct is to create an instance using the placeholders above.

interface TypesDictionary<F = any, A = never, B = never> {
  never: {
    type: never;
    params: never;
    construct: never;
  };
}

type DictKeys = keyof TypesDictionary;

type RegisteredTypes = TypesDictionary[DictKeys]['type'];

type Generic<F extends RegisteredTypes, A = never, B = never> = TypesDictionary<F, A, B>[DictKeys]['construct'];

type TypeParamsOf<F extends RegisteredTypes> = TypesDictionary<F>[DictKeys]['params'];

Creating a generic type

Ok, now for the difficult part: implementing Tuple2 and all its possible type variations.

Here it goes (WARNING: deep ternary nesting ahead):

type Tuple2<L = any, R = any> = [L, R];

interface TypesDictionary<F = any, A = never, B = never> {
  Tuple2: {
    type: Tuple2;
    params: F extends Tuple2 ?
      {
        L: F extends Tuple2<infer L, any> ? L : never;
        R: F extends Tuple2<any, infer R> ? R : never;
      } :
      {};
    construct: F extends Tuple2<_A, _B> ?
      Tuple2<A, B> :
      F extends Tuple2<_B, _A> ?
        Tuple2<B, A> :
        F extends Tuple2<_A, infer R> ?
          Tuple2<A, R> :
          F extends Tuple2<infer L, _A> ?
            Tuple2<L, A> :
            F extends Tuple2<infer L, infer R> ?
              Tuple2<L, R> :
              never;
  };
}

Now imagine having to implement Tuple5!

Testing everything

Ok, now we create some fake types just for testing

type origL = 'L';
type origR = 'R';
type nowA = 'A';
type nowB = 'B';

And put them to the test:

let fixed: Generic<Tuple2<origL, origR>>;
let varyLeft: Generic<Tuple2<_, origR>, nowA>;
let varyRight: Generic<Tuple2<origL, _>, nowA>;
let varyBoth: Generic<Tuple2<_A, _B>, nowA, nowB>;
let varyBothReversed: Generic<Tuple2<_B, _A>, nowA, nowB>;

let paramsFixed: TypeParamsOf<typeof fixed>;
let paramsVaryLeft: TypeParamsOf<typeof varyLeft>;
let paramsVaryRight: TypeParamsOf<typeof varyRight>;
let paramsVaryBoth: TypeParamsOf<typeof varyBoth>;
let paramsVaryBothReversed: TypeParamsOf<typeof varyBothReversed>;

Now open this playground and hover this last section to check if it works (spoiler alert: it does).

[SimonMeskens]

that's interesting and in line with some of what I'm doing, but Tuple2 is not enough, since we're dealing with dynamic Tuples of any length. Off the top of my head there's some really common 3 parameter types and I've already run into a few 4 parameter types in the GenericEither sample. And here's the thing: we don't know at call site how many type parameters the type will have either.

I actually just found a full solution, but I'm missing one primitive:

type Merge<T extends TupleLike, U extends TupleLike>

What this type does is basically the same as your deep ternary. T has placeholders and we need to replace each one in succession with one from U. It's proving hard to write though.

here's an example, where * is the placeholder type:

Merge<[1, *, 3, *, 5], [2, 4]> = [1, 2, 3, 4, 5]

[nadameu]

I see what you're trying to do, but may I point out, while this would work, it would only fill the placeholders in order.

Say you want to change parameters 2 and 4 at the same time, but the interface returns them in the inverse order.

One suggestion I have from watching a lot of math videos on YouTube: try to solve a simpler problem first, perhaps it will give you the tools to solve a harder one.

You might try figuring out something like this first:

Replace<[A, B, C], 1, D> = <[A, D, C]>

The signature would be Replace<TupleLike, Index, Replacement>: TupleLike

[SimonMeskens]

Yeah, I found an implementation for Merge, using exactly that. You are correct that the placeholders still force the order to be left to right, I'll have to add a way to do *1 *2, etc, which should be fairly straightforward.

For reference, here's the Merge:

        type Replace<T extends TupleLike, Index extends number, Element> = {
            [Key in Keys<T>]: Key extends Index ? Element : T[Key]
        };

        type Pop<T extends TupleLike> = util.Simplify<
            {
                [Key in Keys<{ length: util.Subtract<T["length"], 1> }>]: T[Key]
            } & {
                length: util.Subtract<T["length"], 1>;
            }
        >;

        type Merge<
            T extends TupleLike,
            U extends TupleLike,
            Counter extends number = util.Subtract<U["length"], 1>
        > = util.Simplify<
            ({
                [Index in util.Span<Counter>]: Counter extends 0
                    ? ReplacePlaceholder<T, U[Counter]>
                    : Merge<
                          ReplacePlaceholder<
                              T,
                              U[util.Subtract<U["length"], 1>]
                          >,
                          Pop<U>,
                          util.Subtract<Counter, 1>
                      >
            } & {
                [index: number]: never;
            })[Counter] & { length: T["length"] }
        >;

        type ReplacePlaceholder<
            T extends TupleLike,
            U,
            Counter extends number = util.Subtract<T["length"], 1>
        > = ({
            [Index in Keys<T>]: T[Index] extends _
                ? Replace<T, Index, U>
                : ReplacePlaceholder<T, U, util.Subtract<Counter, 1>>
        } & {
            [index: number]: never;
        })[Counter];

Complexity is going way up, so I'm starting to doubt where exactly this library will sit. If we had the abovementioned generic function infer, I could get rid of this whole part though, so I think for now, I'll do it this way and pray we get a resolution down the line.

Part of the existence of this library is the tuple manipulations (the other part being the pattern matcher, which I also can't generalize due to the function infer).

Maybe there's two libraries here? A really simple one that is just a slightly better mousetrap to help with fantasy-land types and the monstrosity this is turning into. I might offer both under different namespaces or even different repos.

[SimonMeskens]

Turns out if you don't need ordering, all the complex code goes away, go figure. Ah well, was a fun night of work.

        const Placeholder: {
            readonly 0: unique symbol;
            readonly 1: unique symbol;
            readonly 2: unique symbol;
            readonly 3: unique symbol;
            readonly 4: unique symbol;
            readonly 5: unique symbol;
            readonly 6: unique symbol;
            readonly 7: unique symbol;
            readonly 8: unique symbol;
            readonly 9: unique symbol;
        };
        type Placeholders = typeof Placeholder[keyof typeof Placeholder];

        type _<
            T extends keyof typeof Placeholder
        > = typeof Placeholder[T] & { index: T };

        type ReplacePlaceholder<T extends TupleLike, U extends TupleLike> = {
            [Index in Keys<T>]: T[Index] extends Placeholders
                ? U[T[Index]["index"]]
                : T[Index]
        };

        type Test = ReplacePlaceholder<[_<1>, _<0>, 2], [3, 4]>;

[nadameu]

Very clean and simple solution!

Can you give me some code example of the problem you are trying to solve with this library? I might think of another approach.

[SimonMeskens]

I'm in the process of finding an writing examples, but the main idea is that something like fp-ts requires you to have Generic, Generic2, Generic3, etc interfaces. My plan from the start was to store type information in tuples, so they can be manipulated. The Placeholder system you suggested is working wonders, I can now say something like [Infer, Infer, _<0>].

I guess the goals are:

• No storing of type information on the types themselves. I accomplish that with the pattern match primitives stored in the type dictionary.
• Parameters are always stored in a tuple, so we don't need Generic2, Generic3, etc.
• Has to work with tagged types (the None in maybe.ts in the examples folder is an example of a tagged type).
• Advanced capabilities to work with these Tuple parameters for things like a generic Monad interface, that is only variadic over one of the parameters.
• Hopefully down the line expose the pattern matcher itself, so you don't HAVE to register types into the type Dictionary. I've tested this to work the minute we get a way to infer generic functions properly in the language.
• In this repo or a new one, store a bunch of common types (pre-register the defaults, such as Array, as well as providing all the static-land, fantasy-land, etc, interfaces).

I've currently proven that all of these are possible and now I'm converting the two examples given to me in #1, which are quite nice examples, as they aren't typable by fp-ts. On top of that, I'm forcing myself to use a generic Monad interface to type them, so I can make sure that use case works.

[SimonMeskens]

I did it! I added the new samples to the repo and I'm getting amazing typing. The examples in question use a form of Monad (Map :: (a -> b) -> T a -> T b) that doesn't lead with the monadic type, but with the operation, so the only issue is that we don't know the actual monad type until late. This means that map gives some really funky type popups, but it works fine.

Unfortunately, I can't give out Playground links until TypeScript 2.9 hits. I needed some of the new features to make it all work properly.

Here's the new TypeProps library + the Monad interface. A LOT of hours went into this, but it's worth it.

import { Generic, TypeTag, _ } from "typeprops";

export interface Monad<Tag extends TypeTag, Map extends ArrayLike<any> = [_]> {
    // Functor
    // map :: (a -> b) -> T a -> T b
    map: <T, U>(
        transform: (value: T) => U
    ) => <M extends Generic<Tag, [T], Map, any>>(
        monad: M
    ) => Generic<Tag, [U], Map, M>;

    // Monad
    // of :: a -> T a
    of: <T>(value: T) => Generic<Tag, [T], Map, never>;
    // chain :: (a -> T b) -> T a -> T b
    chain: <T, M extends Generic<Tag, any>>(
        transform: (a: T) => M
    ) => (monad: Generic<Tag, [T], Map, M>) => M;
}

declare module "typeprops" {
    type _<
        T extends keyof typeof util.Placeholder = 0
    > = typeof util.Placeholder[T] & { index: T };
    type Infer = typeof util.InferSymbol;

    interface TypeProps<T extends any = any> {
        never: {
            infer: T extends never ? { length: 0 } : never;
            construct: never;
        };
    }

    type TypeTag<T = any> = {
        [K in keyof TypeProps]: TypeProps<T>[K]["infer"] extends never
            ? never
            : K
    }[keyof TypeProps];

    type TypeProxy<
        Tag extends keyof TypeProps,
        Map extends ArrayLike<any>,
        T,
        Params extends ArrayLike<any> = ArrayLike<any>
    > = {
        [Key in keyof util.ToTuple<Map>]: Key extends number
            ? Map[Key] extends Infer
                ? T extends never
                    ? never
                    : Key extends keyof TypeParams<T, Tag>
                        ? TypeParams<T, Tag>[Key]
                        : never
                : Map[Key] extends _<infer Index>
                    ? Params[Index]
                    : util.ToTuple<Map>[Key]
            : Map["length"]
    };

    type TypeParams<
        T,
        Tag extends keyof TypeProps = keyof TypeProps
    > = util.ToTuple<
        Infer extends T
            ? {
                  [index: number]: any;
                  length: TypeProps<T>[Tag]["infer"]["length"];
              }
            : TypeProps<T>[Tag]["infer"]
    >;

    type Generic<
        Tag extends keyof TypeProps,
        Params extends ArrayLike<any> = ArrayLike<any>,
        Map extends ArrayLike<any> = {
            [index: number]: _;
            length: Params["length"];
        },
        T = never
    > = TypeProps<TypeProxy<Tag, Map, T, Params>>[Tag]["construct"];

    namespace util {
        const InferSymbol: unique symbol;
        const Placeholder: {
            readonly 0: unique symbol;
            readonly 1: unique symbol;
            readonly 2: unique symbol;
            readonly 3: unique symbol;
            readonly 4: unique symbol;
            readonly 5: unique symbol;
            readonly 6: unique symbol;
            readonly 7: unique symbol;
            readonly 8: unique symbol;
            readonly 9: unique symbol;
        };

        type TupleKey = {
            [index: number]: number;
            1: 0;
            2: 0 | 1;
            3: 0 | 1 | 2;
            4: 0 | 1 | 2 | 3;
            5: 0 | 1 | 2 | 3 | 4;
            6: 0 | 1 | 2 | 3 | 4 | 5;
            7: 0 | 1 | 2 | 3 | 4 | 5 | 6;
            8: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7;
            9: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8;
        };

        type ToTuple<T extends ArrayLike<any>> = {
            [Key in TupleKey[T["length"]] | "length"]: T[Key]
        };
    }
}

[masaeedu]

That looks really nice @SimonMeskens, @nadameu! Could you give some info on "usage patterns" for this? E.g. what does the last parameter in Generic<Tag, [T], Map, never> represent?

I'm thinking of maybe trying out some of this stuff in a small library of instance implementations for native JS types that I have. If I can get accurate API docs for free that's worth whatever extra type noise I have to add I think.

[SimonMeskens]

So Generic<Tag, [T]> just means a HKT of type Tag (you can get tags with TypeTag<T>). The two other parameters come in when are writing code that is parametric over one type, but the type you give it potentially has multiple parameters.

I will eventually write some easier examples and documentation of course, but the gist of it is this:

Generic<"either", [number], [Infer, _], Either<string, string>> == Either<string, number>

so we take some either type, give it one parameter, then give it a map, which says "infer the first parameter, replace the second" and a type with parameters [string, string]. The resulting type is the same as Generic<"either", [string, number]>.

I'm hoping I can improve the API in such a way that this will become easier to work with, but this was needed to represent the Haskell concept of Monad (Either e). I have a solution planned that works more like Haskell, which is easier to work with, but that one is still in the works.

[SimonMeskens]

This one is now resolved too. Basically, I allow for combining type dictionaries, so you can have a MonadProps extends FunctorProps and combine that with the type dictionary. There's samples in the repo under lib/abstract/monad and examples/abstract/monad. This most closely mirrors Haskell's instance types, so it makes sense. It also heavily simplified my codebase.