Implement type AST and infer generics

Toy language type system: AST + generic inference

You are implementing a tiny type system for a toy language with:

• Primitive types : char , int , float
• Generic type variables : identifiers like T1 , T2 , … (stand for an unknown type)
• Tuple types : an ordered tuple of 2 or more types, where each element can itself be a primitive, a generic, or another tuple.

Assume the textual syntax for a type is:

• Primitive: char | int | float
• Generic: T followed by one or more digits (e.g., T1 , T20 )
• Tuple: (<type>,<type>,...,<type>) with no restriction on nesting (e.g., (int,(T1,char),float) )

Part A — Node type representation

Implement a Node class/struct that can represent any type in this grammar.

Part B — toString()

Implement toString() for Node that serializes the type back into the exact canonical format described above.

Part C — infer_return(pattern, concrete)

Implement a function that infers what each generic (T1, T2, …) must be, given:

• pattern : a type expression that may contain generics
• concrete : a fully concrete type expression containing no generics (only primitives and tuples)

The function must return a mapping like {T1 -> int, T2 -> (char,float)} such that substituting generics in pattern produces exactly concrete.

Rules

• If pattern is a primitive, it must equal concrete .
• If pattern is a generic Tk , bind it to concrete unless it was already bound to a different type (conflict).
• If pattern is a tuple, concrete must also be a tuple of the same length, and inference recurses element-wise.

Error cases (must throw/return error)

• Tuple vs non-tuple mismatch
• Tuple length mismatch
• Primitive mismatch
• Conflicting generic bindings (e.g., pattern=(T1,T1) with concrete=(int,float) )

Examples

• pattern=(T1,int) , concrete=(char,int) → {T1 -> char}
• pattern=(T1,(T2,char)) , concrete=(float,(int,char)) → {T1 -> float, T2 -> int}
• pattern=(T1,T1) , concrete=(int,float) → error (conflict)

State any assumptions about parsing/whitespace and how you represent/compare types.