Simulating Generalized Algebraic Data Types (GADTs) in TypeScript

GADTs are a powerful feature in functional programming languages like Haskell, allowing for more precise type definitions and improved type safety. While TypeScript doesn't natively support GADTs, we can simulate their behavior using discriminated unions and conditional types. This challenge asks you to create a system that mimics the core functionality of GADTs, enabling you to define data types with varying constructors and associated types.

Problem Description

The goal is to implement a simplified GADT simulation in TypeScript. You will define a base type GADTs and then create several concrete "data types" that inherit from it, each with its own specific constructor and associated type. The simulation should enforce that the associated type of a constructor is used correctly when accessing the data. This means that when you extract data from a GADT instance, the compiler should be able to infer the correct type based on the constructor used.

Specifically, you need to create the following GADT-like types:

1. Option<A>: Represents a value that may or may not be present. It has two constructors: Some(value: A) and None().
2. List<A>: Represents a list of elements of type A. It has two constructors: Cons(head: A, tail: List<A>) and Nil().
3. Tree<A>: Represents a binary tree where each node holds a value of type A. It has two constructors: Leaf(value: A) and Node(left: Tree<A>, right: Tree<A>).

You should implement functions to create instances of these types and functions to extract data from them, ensuring type safety.

Examples

Example 1: Option

Input: createOption(10)
Output: { type: "Some", value: 10 }
Explanation: Creates an Option containing the value 10.

Input: createOption()
Output: { type: "None" }
Explanation: Creates an Option with no value.

Input: getValue(createOption(20))
Output: 20
Explanation: Extracts the value from a Some Option.  Should result in type inference of number.

Input: getValue(createOption())
Output: Error: No value in None option.
Explanation: Attempts to extract a value from a None Option, resulting in an error.

Example 2: List

Input: createList(1, 2, 3)
Output: { type: "Cons", head: 1, tail: { type: "Cons", head: 2, tail: { type: "Cons", head: 3, tail: { type: "Nil" } } } }
Explanation: Creates a list containing the values 1, 2, and 3.

Input: createList()
Output: { type: "Nil" }
Explanation: Creates an empty list.

Input: getHead(createList(5, 6))
Output: 5
Explanation: Extracts the head of a non-empty list. Should result in type inference of number.

Input: getHead(createList())
Output: Error: Cannot get head of an empty list.
Explanation: Attempts to extract the head of an empty list, resulting in an error.

Example 3: Tree

Input: createTree(10, 5, 15)
Output: { type: "Node", left: { type: "Leaf", value: 5 }, right: { type: "Leaf", value: 15 } }
Explanation: Creates a tree with a root value of 10 and left and right leaves with values 5 and 15 respectively.

Input: getRootValue(createTree(20, 1, 3))
Output: 20
Explanation: Extracts the root value of a tree. Should result in type inference of number.

Constraints

• All data types must be represented as objects with a type property indicating the constructor used.
• The type property must be a string literal type (e.g., "Some", "Cons", "Leaf").
• The getValue function for Option must throw an error if called on a None option.
• The getHead function for List must throw an error if called on an empty list (Nil).
• The getRootValue function for Tree must throw an error if called on a Leaf node.
• Type safety is paramount. The compiler should be able to infer the correct type based on the constructor used.
• The solution should be reasonably well-structured and readable.

Notes

• Consider using discriminated unions to represent the different constructors.
• TypeScript's conditional types can be helpful in enforcing type safety when extracting data.
• You don't need to implement all possible operations for these data types; focus on demonstrating the core GADT simulation concept.
• Think about how to represent the associated types (e.g., A in Option<A>) in TypeScript. Using generics is key.
• Error handling should be explicit and informative.