Hone logo
Hone
Problems

Type-Level Topological Sort in TypeScript

Type-level programming allows us to perform computations at compile time, enabling powerful abstractions and optimizations. This challenge asks you to implement a topological sort algorithm operating entirely at the type level in TypeScript. This is useful for ensuring dependencies between types are met before they are used, preventing runtime errors by catching them during compilation.

Problem Description

You need to create a TypeScript type TopologicalSort<T> that takes a tuple of types T representing a directed acyclic graph (DAG) and returns a new tuple with the types sorted topologically. A topological sort orders the nodes (types) of a DAG such that for every directed edge from node A to node B, node A comes before node B in the ordering. If the input graph contains cycles, the type should error out at compile time.

Key Requirements:

  • DAG Assumption: The input tuple T represents a DAG. Your solution must error out if a cycle is detected.
  • Type-Level Only: The sorting must be performed entirely at the type level, without runtime execution.
  • No External Libraries: You should not use any external libraries.
  • Error Handling: If a cycle is detected, the compiler should produce a meaningful error message.
  • Order Preservation: If there are no dependencies between two types, their relative order in the output tuple should be the same as in the input tuple.

Expected Behavior:

The TopologicalSort<T> type should produce a new tuple where the types are ordered such that all dependencies are satisfied. The order of independent types should be preserved. Cycles should result in a compile-time error.

Edge Cases to Consider:

  • Empty input tuple: Should return an empty tuple.
  • Tuple with a single type: Should return the same tuple.
  • Cycles in the graph: Should result in a compile-time error.
  • Multiple possible topological orderings: Any valid topological ordering is acceptable.

Examples

Example 1:

type Graph = [A, B, C, D, E];

// A -> B, A -> C, B -> D, C -> D, D -> E
type Sorted = TopologicalSort<Graph>; // Expected: [A, B, C, D, E] or [A, C, B, D, E] (any valid topological sort)

Example 2:

type Graph2 = [A, B, C];

// A -> B, B -> C, C -> A (Cycle!)
type Sorted2 = TopologicalSort<Graph2>; // Expected: Compile-time error indicating a cycle.

Example 3:

type Graph3 = [A, B, C, D];

// A -> B, C -> D
type Sorted3 = TopologicalSort<Graph3>; // Expected: [A, B, C, D] or [C, D, A, B] or [A, C, B, D] etc. (any valid topological sort)

Constraints

  • The input tuple T can contain any number of types (0 or more).
  • Types can be any valid TypeScript type.
  • The algorithm should be efficient enough to handle tuples with up to 10 types without excessive compile times. (While compile time is a factor, prioritize correctness and clarity over extreme optimization).
  • The cycle detection mechanism should provide a reasonably informative error message to aid debugging.

Notes

  • This is a challenging problem that requires a good understanding of TypeScript's type system and conditional types.
  • Consider using recursive conditional types to explore the dependencies between types.
  • Cycle detection can be implemented by tracking visited types during the traversal. A type-level "visited" set can be maintained.
  • The order of types that are not dependent on each other is not strictly defined, so any valid topological ordering is acceptable.
  • Focus on creating a robust and understandable solution, even if it's not the most performant. Compile-time performance is less critical than correctness in this scenario.
Loading editor...
typescript