Simulating Generalized Algebraic Data Types (GADT) in TypeScript

This challenge focuses on simulating the expressive power of Generalized Algebraic Data Types (GADTs) in TypeScript. GADTs allow defining data types where the structure of the data is tied to the type itself, enabling more precise type-level reasoning and safer manipulation of data. This exercise will help you understand how to leverage TypeScript's type system to achieve similar benefits, particularly in scenarios involving discriminated unions and type-safe pattern matching.

Problem Description

Your task is to create a TypeScript implementation that simulates the behavior of GADTs. Specifically, you need to define a mechanism for creating data types that have constructors returning different types based on a type parameter, and then implement a type-safe way to "match" or "switch" on these GADT-like structures.

You should aim to achieve the following:

• Define GADT-like structures: Create a way to define data types where a constructor's return type depends on a specific type parameter. This is often seen in functional programming languages for tasks like representing computations or parsing.
• Type-safe pattern matching: Implement a function or method that allows you to safely deconstruct these GADT-like structures. This matching mechanism should ensure that you handle all possible cases and that the types within each case are correctly inferred and checked by the TypeScript compiler.
• Immutability: The simulated GADT structures and their manipulation should ideally be immutable.

Key Requirements:

1. GADT<Tag, Value> type: Define a generic type GADT<Tag, Value> that represents your GADT. Tag will be a type that discriminates between different constructors, and Value will be the type of data associated with that constructor.
2. Constructor functions: For each "constructor" of your GADT, provide a function that creates an instance of GADT. The return type of these functions should be specific to the Tag they represent.
3. match function: Implement a match function that takes a GADT instance and an object of handler functions. Each handler function in the object should correspond to a specific Tag. The match function should ensure that:
   • All possible Tag types are handled.
   • The Value type within each handler is correctly typed according to the corresponding Tag.
   • The match function returns a value based on the executed handler.

Expected Behavior:

When you define a GADT-like structure using your GADT type and constructor functions, and then use the match function to process an instance of it, TypeScript should enforce that all possible cases are handled. If a case is missed, the compiler should raise an error. Similarly, within each handler, the type of the data associated with that case should be correctly inferred.

Edge Cases:

• Empty GADT: Consider how your system would behave with a GADT that has no constructors (though less practical, it's a good theoretical consideration).
• Complex Value types: Ensure your system correctly handles Value types that are themselves unions, complex objects, or other GADTs.

Examples

Example 1: Simulating a simple Result type (Success/Failure)

Let's represent a Result type that can either be a Success with a value or a Failure with an error.

GADT Definition (Conceptual):

// Imagine this as our GADT, though we'll implement it with types
type Result<T, E> = Success<T> | Failure<E>;

type Success<T> = { __tag: 'Success', value: T };
type Failure<E> = { __tag: 'Failure', error: E };

TypeScript Implementation Simulation:

Let's define a ResultGADT where the tag is 'Success' or 'Failure', and the value is the corresponding data.

Input:

// Define the possible tags
type ResultTag = 'Success' | 'Failure';

// Define the GADT type
type ResultGADT<T, E, Tag extends ResultTag> = GADT<Tag, Tag extends 'Success' ? T : E>;

// Constructor functions
function Success<T, E>(value: T): ResultGADT<T, E, 'Success'> {
  return { __tag: 'Success', value } as any; // Type assertion for simulation
}

function Failure<T, E>(error: E): ResultGADT<T, E, 'Failure'> {
  return { __tag: 'Failure', error } as any; // Type assertion for simulation
}

// A simplified GADT base type (for demonstration purposes)
interface GADT<Tag, Value> {
  __tag: Tag;
  value: Value;
}

// The match function (simplified for this example)
function matchResult<T, E, R>(
  result: ResultGADT<T, E, any>, // `any` is used here to allow passing either Success or Failure
  handlers: {
    Success: (value: T) => R;
    Failure: (error: E) => R;
  }
): R {
  switch (result.__tag) {
    case 'Success':
      return handlers.Success(result.value);
    case 'Failure':
      return handlers.Failure(result.error);
  }
}

// Usage
const successResult: ResultGADT<number, string, 'Success'> = Success<number, string>(10);
const failureResult: ResultGADT<number, string, 'Failure'> = Failure<number, string>('Something went wrong');

const successOutput = matchResult(successResult, {
  Success: (val) => `Successfully got: ${val}`,
  Failure: (err) => `Operation failed: ${err}`,
});

const failureOutput = matchResult(failureResult, {
  Success: (val) => `Successfully got: ${val}`,
  Failure: (err) => `Operation failed: ${err}`,
});

console.log(successOutput); // Output: Successfully got: 10
console.log(failureOutput); // Output: Operation failed: Something went wrong

Explanation:

The ResultGADT type uses a Tag to differentiate between Success and Failure. The Success constructor returns a ResultGADT where the Tag is 'Success' and the Value is of type T. The Failure constructor similarly returns a ResultGADT with Tag 'Failure' and Value of type E. The matchResult function ensures that both Success and Failure handlers are provided. If you try to omit one, TypeScript will complain. Inside the Success handler, val is correctly typed as T, and inside the Failure handler, err is correctly typed as E.

Example 2: Simulating a simple Shape type (Circle/Rectangle)

Let's define a GADT to represent different geometric shapes.

Input:

// Define the possible tags
type ShapeTag = 'Circle' | 'Rectangle';

// Define the GADT base type
interface GADT<Tag, Value> {
  __tag: Tag;
  value: Value;
}

// Define the GADT type for Shapes
type ShapeGADT<Tag extends ShapeTag> =
  Tag extends 'Circle'
    ? GADT<'Circle', { radius: number }>
  : Tag extends 'Rectangle'
    ? GADT<'Rectangle', { width: number; height: number }>
    : never; // Should not happen

// Constructor functions
function Circle(radius: number): ShapeGADT<'Circle'> {
  return { __tag: 'Circle', value: { radius } } as any;
}

function Rectangle(width: number, height: number): ShapeGADT<'Rectangle'> {
  return { __tag: 'Rectangle', value: { width, height } } as any;
}

// The match function
function matchShape<R>(
  shape: ShapeGADT<'Circle'> | ShapeGADT<'Rectangle'>, // Union of all possible ShapeGADT instances
  handlers: {
    Circle: (circleData: { radius: number }) => R;
    Rectangle: (rectData: { width: number; height: number }) => R;
  }
): R {
  switch (shape.__tag) {
    case 'Circle':
      return handlers.Circle(shape.value);
    case 'Rectangle':
      return handlers.Rectangle(shape.value);
  }
}

// Usage
const myCircle: ShapeGADT<'Circle'> = Circle(5);
const myRectangle: ShapeGADT<'Rectangle'> = Rectangle(4, 6);

const circleArea = matchShape(myCircle, {
  Circle: (data) => Math.PI * data.radius ** 2,
  Rectangle: (data) => data.width * data.height, // This handler won't be called for a Circle
});

const rectangleArea = matchShape(myRectangle, {
  Circle: (data) => Math.PI * data.radius ** 2,
  Rectangle: (data) => data.width * data.height,
});

console.log(`Circle area: ${circleArea}`);
console.log(`Rectangle area: ${rectangleArea}`);

Explanation:

Here, ShapeGADT<Tag> is defined to return a specific GADT structure based on the Tag. Circle constructor returns GADT<'Circle', { radius: number }> and Rectangle returns GADT<'Rectangle', { width: number; height: number }>. The matchShape function, when given a union of all possible ShapeGADT instances, correctly infers the type of data within each handler.

Constraints

• The GADT simulation must be implemented entirely in TypeScript.
• The solution should leverage TypeScript's type system for compile-time safety.
• The match function must enforce exhaustiveness for the defined Tag types.
• There should be no runtime type checks; all safety should be provided by the compiler.
• The GADT simulation should be general enough to define multiple types with different tag and value combinations.

Notes

• Think about how to represent the Tag and Value within your GADT type. A common approach is to use a discriminated union pattern.
• For the match function, consider how to ensure all possible Tag types are handled. Conditional types and union types will be your friends here.
• The use of as any in the constructor functions is a common TypeScript pattern when simulating complex type relationships that are hard for the compiler to infer perfectly on its own. The goal is for the match function to provide the ultimate type safety.
• This exercise is about simulating GADTs. You won't be able to achieve the full expressiveness of language-level GADTs, but you can get very close in terms of type safety for specific use cases.
• Consider how to make your match function truly generic, accepting any GADT-like structure defined with your GADT base type.