Type Signature Serialization & Inference — OpenAI

You must design a small, readable textual format for type signatures and implement data structures and an inference routine that work with that format.

Start by defining a concise serialization that can express primitive types (char, int, float, str), named type variables (T1, T2), tuples (e.g. [int, char]), and function types (params -> return). The format must be deterministic so identical types always serialize to the same string, and tuple/parameter lists must be unambiguous (for example, bracketed lists and a parenthesized parameter list with ->).

Implement a Node abstraction that represents either an atomic type (primitive or named variable) or a tuple (a list of child Nodes). Implement a Function abstraction that holds an ordered list of parameter Nodes and a single output Node, with stable to_str serialization for both Node and Function.

Implement type-variable inference: given a Function signature that may contain named type variables and a list of concrete parameter Nodes (no generics), infer a mapping from each type variable to a concrete Node and return the output Node with variables substituted. Your inference must check for incorrect argument counts, structural mismatches (tuple arity/shape), and conflicting assignments for the same type variable and raise clear exceptions.

Flow in an interview: describe the format, implement Node/Function, write deterministic to_str, then implement structural matching and unification-style inference, and test with positive and negative examples. Skills signaled: tree traversal, unification/type inference, deterministic serialization, and careful error handling.