Are there recommendations for binding type-level functions to runtime implementations ?

[GautierBlandin]

The library's documentation showcases a very elegant type-level function pipeline:

interface Append<Suffix extends string> extends TypeLambda<[s: string], string> {
  return: `${Arg0<this>}${Suffix}`;
}

type ConcatNames = Flow<
  Filter<Flow<StringLength, NotExtend<1 | 2>>>,
  Take<3>,
  Map<CapitalizeString>,
  JoinBy<", ">,
  Append<", ...">
>;

type Names = ["alice", "bob", "i", "charlie", "david"];
type _ = Call1<ConcatNames, Names>; // => "Alice, Bob, Charlie, ..."

After experimenting with the lib, a common need that I ended up having is the ability to bind type-lambdas to a runtime implementation, and to be able to compose them together.

I have made a primitive attempt using the following approach:

export interface TypeLambdaFn<
  L extends TypeLambda1,
> extends TypeLambdaFnBrand<L> {
  <const A>(value: A): Call1<L, A>;
}

A common pattern I have encountered is the definition of type-lambda functions that both accept another type-lambda function as input, and return a type-lambda function as output.

Example application with a tag-based dependent-typing library:

// dependent.ts
export const flowUniform = <F extends TypeLambdaFn<any>>(
  f: F,
): TypeLambdaFn<FlowUniformLambda<ExtractLambda<F>>> => { ... }

// consumer.ts
const evolve = A.fn((_a: A) =>
      Dep.match({ B: (_b: B) => 'A-B' as const, C: (_c: C) => 'A-C' as const }),
    );

const mapped = pipe(evolve, Dep.flowUniform(Dep.flowUniform(Result.okL)));

typeof evolve (inferred):

const evolve: Dep.DepFn<{
  A: {
    in: [A]
    out: Dep.DepFn<{
      B: {
        in: [_b: B]
        out: 'A-B'
      }
      C: {
        in: [_c: C]
        out: 'A-C'
      }
    }>
  }
}>

typeof mapped (inferred):
const mapped: Dep.DepFn<{
  A: {
    in: [A]
    out: Dep.DepFn<{
      B: {
        in: [_b: B]
        out: Result.Result<'A-B', never>
      }
      C: {
        in: [_c: C]
        out: Result.Result<'A-C', never>
      }
    }>
  }
}>

I was wondering if you had experimented with approaches around the interaction of type-level functions and runtime functions. I find the ability to write properly generic runtime functions (that is, generic function that correctly compose with other generic functions) extremely compelling.

[Snowflyt]

Thanks for taking a close look at hkt-core and sharing this idea!

I think this is a very clever approach, and I really like the design direction. Using a phantom type to let a runtime function carry its corresponding TypeLambda seems reasonable to me. It gives runtime functions a stable type-level representation that other combinators can inspect and transform.

I tried to reproduce the idea here.

In my own code, when I need both a runtime generic function and a type-level lambda, I usually end up maintaining two parallel definitions: one runtime implementation and one type-level implementation. Your approach suggests a more structured bridge between the two, which is very interesting.

I have also run into related problems around type-level lambdas and runtime generic function types. This may not be exactly the same problem as the one you are pointing out, but I think it is still worth mentioning.

In the past, I wanted to compose generic function types at the type level, with semantics similar to flow(...) in libraries like fp-ts. Unfortunately, TypeScript does not seem to provide a general way to "simulate a call" and obtain the resulting expression type, like one might do with decltype(...) in C++.

For example, what I wanted was something conceptually like:

type CombinedFunctionType =
  decltype(flow(
    42 as unknown as GenericFunctionTypeA,
    42 as unknown as GenericFunctionTypeB
  ));

But TypeScript does not have such a mechanism. Value-level flow(genericFnA, genericFnB) can sometimes preserve generic inference because the compiler has special inference behavior for real function calls, but that machinery is not generally available inside a type alias.

One workaround I have used with hkt-core is to define those generic function types first as TypeLambdaGs, compose them using hkt-core’s Flow, and only then turn the result into a runtime function type with Sig:

type GenericFunctionType = Sig<GenericFunctionTypeLambda>;

This is quite hacky, because Sig was originally designed as a debugging / inspection utility rather than a stable API for generating runtime function types. I also cannot promise that its exact behavior will remain stable in the future. Still, in practice, it can be useful for some experiments.

[GautierBlandin]

I accidentally clicked the complete issue button while working on a message draft and do not have permission to re-open it.

[Snowflyt]

I accidentally clicked the complete issue button while working on a message draft and do not have permission to re-open it.

No worries, I’ve reopened it.

[GautierBlandin]

I'm very impressed that you managed a working repro this fast, especially for the dependent-typed part !

As I've explored the direction, the design challenges that I've encountered include:

• Implementation soundness of type-lambda functions (for instance, it is possible to soundly implement the ok function outside of the type-lambda world). Can the soundness be maintained when moving over to type-lambda functions ?

In the ok example, this seemed achievable:

export interface OkLambda extends TypeLambda1 {
  return: Result<Arg0<this>, never>;
}

export const liftFn = <L extends TypeLambda1>(
  f: <A>(value: A) => Call1<L, A>,
): TypeLambdaFn<L> => f as TypeLambdaFn<L>;

// good
export const okL = liftFn<OkLambda>(ok);

// bad
export const okL = liftFn<OkLambda>(err);

TS2345: Argument of type <E>(error: E) => Result<never, E> is not assignable to parameter of type <A>(value: A) => Result<A, never>
Type Result<never, A> is not assignable to type Result<A, never>
Type Left<A, never> is not assignable to type Result<A, never>
Type Left<A, never> is not assignable to type Left<never, A>
Type A is not assignable to type never

• "Pretty" inferred type signature.

In my code, here is the inferred signature of okL: export const okL: TypeLambdaFn<OkLambda>
Ideally, we'd probably want the inferred signature to look like <T>(value: T): Result<T, never> & TypeLambdaFnBrand<OkLambda>. This may be achievable by leveraging Sig alongside a TypeLambdaG (I still have to do some work to properly understand TypeLambdaGs, so far I've mostly used simple HKTs / TypeLambdas).

• Composition soundness

That's another point that should likely be solvable by leveraging TypeLambdaG to make the original ConcatNames type-level example workable and should through runtime composition.

• Interoperability with non-type-lambda code

My experience so far when working on highly-generic fp code is that library code should always interop seamlessly with "standard" code. For instance, a significant problem with the flowUniform utility that I showed earlier is that in only accepts TypeLambdaFns. This means that a concrete function with signature, e.g., (x: number) => number won't bind well into it. This could be solved with something like a liftConcrete helper, or more elegantly by having a generic that automatically lifts a concrete signature into its type-lambda equivalent.

Would you be interested in collaborating on an extension to hkt-core to structure the runtime / type-level binding at some point ? It's something that I intended to be do anyway in our internal codebase, but if you see value to it, I'd be very happy to work on this in an open-sourced setting.
I don't think this should be part of hkt-core though, since it will inherently have associated runtime behaviors.

[GautierBlandin]

But TypeScript does not have such a mechanism. Value-level flow(genericFnA, genericFnB) can sometimes preserve generic inference because the compiler has special inference behavior for real function calls, but that machinery is not generally available inside a type alias.

Interesting, I have never managed to get flow(genericA, genericB) working well. pipe(concrete, genericA, genericB) always work well, but of course it doesn't work well for defining functions: you end up having to write your own typings, with the opportunity to create unsoundness.

[Snowflyt]

I'm very impressed that you managed a working repro this fast, especially for the dependent-typed part !

As I've explored the direction, the design challenges that I've encountered include:

* Implementation soundness of type-lambda functions (for instance, it is possible to soundly implement the `ok` function outside of the type-lambda world). Can the soundness be maintained when moving over to type-lambda functions ?

In the ok example, this seemed achievable:

export interface OkLambda extends TypeLambda1 {
  return: Result<Arg0<this>, never>;
}

export const liftFn = <L extends TypeLambda1>(
  f: <A>(value: A) => Call1<L, A>,
): TypeLambdaFn<L> => f as TypeLambdaFn<L>;

// good
export const okL = liftFn<OkLambda>(ok);

// bad
export const okL = liftFn<OkLambda>(err);

TS2345: Argument of type <E>(error: E) => Result<never, E> is not assignable to parameter of type <A>(value: A) => Result<A, never>
Type Result<never, A> is not assignable to type Result<A, never>
Type Left<A, never> is not assignable to type Result<A, never>
Type Left<A, never> is not assignable to type Left<never, A>
Type A is not assignable to type never

* "Pretty" inferred type signature.

In my code, here is the inferred signature of okL: export const okL: TypeLambdaFn<OkLambda> Ideally, we'd probably want the inferred signature to look like <T>(value: T): Result<T, never> & TypeLambdaFnBrand<OkLambda>. This may be achievable by leveraging Sig alongside a TypeLambdaG (I still have to do some work to properly understand TypeLambdaGs, so far I've mostly used simple HKTs / TypeLambdas).

* Composition soundness

That's another point that should likely be solvable by leveraging TypeLambdaG to make the original ConcatNames type-level example workable and should through runtime composition.

* Interoperability with non-type-lambda code

My experience so far when working on highly-generic fp code is that library code should always interop seamlessly with "standard" code. For instance, a significant problem with the flowUniform utility that I showed earlier is that in only accepts TypeLambdaFns. This means that a concrete function with signature, e.g., (x: number) => number won't bind well into it. This could be solved with something like a liftConcrete helper, or more elegantly by having a generic that automatically lifts a concrete signature into its type-lambda equivalent.

Would you be interested in collaborating on an extension to hkt-core to structure the runtime / type-level binding at some point ? It's something that I intended to be do anyway in our internal codebase, but if you see value to it, I'd be very happy to work on this in an open-sourced setting. I don't think this should be part of hkt-core though, since it will inherently have associated runtime behaviors.

Thanks for the detailed breakdown. I think these are exactly the right design questions for this direction.

For implementation soundness, the liftFn example you gave does seem to guarantee this kind of soundness at the call-signature level. I believe this approach can keep working. The only slightly awkward part is that the function shape has to be written manually:

<A>(value: A) => Call1<L, A>

This is exactly the kind of boilerplate that TypeLambdaG + Sig may help with. In fact, the TS Playground repro I shared earlier already uses this trick:

import type { RawArg0, RawTArg, Call1W, TypeLambda, TypeLambda1, TypeLambdaG, Sig } from "hkt-core";

declare const TypeLambdaFnSymbol: unique symbol;

interface TypeLambdaFnBrand<L extends TypeLambda<never, unknown>> {
  readonly [TypeLambdaFnSymbol]: L;
}

type ExtractLambda<F> = F extends TypeLambdaFnBrand<infer L> ? L : never;

type TypeLambdaFn<L extends TypeLambda<never, unknown>> = Sig<L> & TypeLambdaFnBrand<L>;

interface OkL extends TypeLambdaG<["T"]> {
  signature: (value: RawTArg<this, "T">) => Call1W<this, RawTArg<this, "T">>;
  return: Result<RawArg0<this>, never>;
}

const ok = <const T>(value: T): Result<T, never> => ({ _tag: "Ok", value });

const okL = ok as TypeLambdaFn<OkL>;

So instead of manually writing the callable signature for each L, we can let the lambda itself describe the signature and then attach the brand.

For the pretty inferred signature problem, this is something I have spent quite a lot of time looking into, because I care about hover / LSP readability in several libraries I work on.

There are a few TypeScript tricks that can help here.

One is that TypeScript tends to hide named interfaces more often, while expanding type aliases more often. My understanding is that interfaces are treated more like real named types internally, while type aliases are more transparent aliases. Similarly, object literal types such as { a: string } also create anonymous internal object types, which affects how the LSP chooses to display them. This behavior is not completely predictable, and I am still exploring it, but the choice between interface and type can make a visible difference.

Another trick is forcing evaluation of a computed object type at the end:

type Evaluate<T> =
  T extends infer R
    ? { [K in keyof R]: R[K] }
    : never;

This often makes the hover display much better for object types produced by a long chain of type-level computation. However, this only really applies to object types.

For function signatures, I think the Sig<L> & TypeLambdaFnBrand<L> shape used in my repro may be helpful. It lets the callable part remain visible while still carrying the phantom lambda brand.

That said, the brand part is a little tricky. As far as I know, TypeScript tends to evaluate both interfaces and intersections lazily, so I am not completely sure whether we can always get a truly pretty hover signature for the branded case.

One small trick that may help is adding an extra type parameter only for display:

type TypeLambdaFn<
  L extends TypeLambda<never, unknown>,
  S = Sig<L>,
> = S & TypeLambdaFnBrand<L>;

Here S is not really needed semantically. It just gives the LSP a chance to display something like:

TypeLambdaFn<OkL, <T>(value: T) => Result<T, never>>

I am not sure this is the final solution, but this kind of display-oriented type parameter can sometimes make complex branded types much easier to inspect.

For composition soundness, I think Flow is probably the right building block. I would also recommend experimenting with TypeLambdaG here. The documentation has several examples around generic type-level functions and composition, and reading some of the hkt-core source code may also help, although some parts are admittedly quite hacky.

For example, the kind of direction I have in mind is roughly:

type RuntimeFlow<F, G> =
  TypeLambdaFn<Flow<ExtractLambda<F>, ExtractLambda<G>>>;

where the runtime implementation composes the actual functions, while the type-level side composes the carried lambdas with Flow. The hard part is making sure these two stay aligned.

For interoperability with non-type-lambda code, I agree this is a tricky problem. The main limitation is TypeScript itself. I do not think we can generally lift an arbitrary generic runtime function into a TypeLambdaG, because TypeScript does not expose the generic inference machinery of value-level calls at the type level.

So I currently think the direction is mostly one-way (TypeLambdaG -> Sig<L> -> runtime function type).

Concrete non-generic functions may be liftable with helper APIs, but fully generic functions probably need users to provide the corresponding TypeLambdaG explicitly.

I also agree that anything involving runtime behavior should probably not live directly in hkt-core. I would be very happy to see something in the surrounding ecosystem though. Names like hkt-core-runtime or hkt-core-fn sound reasonable to me, although the package does not necessarily have to be tied to the hkt-core name.

My view is that hkt-core should stay as a small core library. What you are describing feels more like a runtime/type-level bridge built on top of hkt-core. It may use hkt-core as one supported representation, but it does not have to be limited to hkt-core’s own scope.

A rough analogy is Standard Schema: many runtime validators support it, but they are not necessarily designed around Standard Schema itself. They use it as an interoperability layer. I could imagine your library having a similar relationship with hkt-core.

[Snowflyt]

One more note about Sig.

Although I used Sig several times in the examples above, I am not completely sure it is the right abstraction to rely on for this use case.

Sig is not only a utility for turning a TypeLambda into a runtime function type. It also does several extra transformations for readability. For example, when the signature contains nested TypeLambdas, Sig may try to display them as runtime function types as well. This is useful for debugging and hover display, but it also means Sig is more of an inspection tool than a minimal, stable runtime-function-type adapter.

If this direction becomes something people actually build on, I think it would probably be better to implement a dedicated helper based on the ideas in Sig, but with a narrower and more stable purpose: converting a TypeLambda / TypeLambdaG into its callable runtime function type. It could be called something like Callable<L> or RuntimeFn<L>.

I do think this is a good idea, and maybe I can provide such a helper in a future version of hkt-core. However, I am currently busy with some work-related things, so this may need to wait for a while.

The implementation would also be somewhat complex. It would need to handle many edge cases, especially around TypeLambdaG, so I would prefer not to rush it or expose something unstable too early.