Implement toy-language types and generic substitution

Problem: Toy Language Type System (Printing + Generic Resolution)

You are implementing a small type system for a custom “Toy Language”. Types can be:

• Primitive types: lowercase strings like int, float, str, bool
• Generic type variables: uppercase letter(s) followed by digits, e.g., T1, T2
• Tuples: bracketed, comma-separated types, which may be nested, e.g. [int,[T1,str]]
• Function signatures: a list of parameter types and a single return type, written as (param1,param2,...) -> returnType

Data structures

Implement the following classes.

Node

Represents a type node.

• Construction:
  • If node_type is a string, the node is a leaf representing either a primitive type or a generic.
  • If node_type is a list of Node, the node is a tuple whose children are those nodes.

class Node:
    def __init__(self, node_type):
        ...

    def to_str(self) -> str:
        ...

Node.to_str() formatting rules

• Leaf: return the exact string name, e.g. "int", "T1".
• Tuple: return bracketed, comma-separated children with no spaces, e.g. [int,T1], [int,[T1,str]].

Function

Represents a function signature.

class Function:
    def __init__(self, parameters: list[Node], output_type: Node):
        ...

    def to_str(self) -> str:
        ...

Function.to_str() formatting rules

• Format: (param1,param2,...) -> returnType using each node’s to_str().
• Example: (int,T1) -> [T1,str]

---

Part 2: Infer concrete return type

Implement:

def get_return_type(parameters: list[Node], function: Function) -> Node:
    ...

Given:

• function.parameters: the expected parameter type patterns (may include generics and nested tuples)
• parameters: the actual argument types supplied at a call site

Return a new Node representing the concrete return type after substituting generics.

Requirements

1. Argument count check

   • Raise an error if len(parameters) != len(function.parameters).

2. Build a substitution table (generic resolution)

   • Compare each expected parameter pattern against the corresponding actual argument type.
   • If the expected node is a generic (e.g., T1), bind it to the actual type node.
   • If the expected node is a primitive, it must match the actual primitive exactly.
   • If the expected node is a tuple, the actual must also be a tuple of the same arity, and you must recurse.

3. Conflict detection

   • If a generic like T1 is bound more than once in the same call, all bindings must be structurally identical.
   • Otherwise raise an error (e.g., T1 cannot be both int and str).

4. Return type substitution

   • After building the mapping, recursively replace all generics appearing in function.output_type with their bound concrete types.
   • If a generic appears in the output type but was never bound by the inputs, raise an error (or clearly document and implement a consistent behavior).

Examples

1. Basic substitution

   • Function: [T1, T2, int, T1] -> [T1, T2]
   • Arguments: [int, str, int, int]
   • Mapping: T1 = int, T2 = str
   • Result: [int, str]

2. Nested tuples & complex generics

   • Function: [[T1, float], T2, T3] -> [T3, T1]
   • Arguments: [[str, float], [int, str], int]
   • Mapping: T1 = str, T2 = [int, str], T3 = int
   • Result: [int, str]

3. Conflict error

   • Function: [T1, T1] -> T1
   • Arguments: [int, str]
   • Error: T1 cannot be both int and str

Implement the above behavior with clear recursive logic and appropriate error handling.

Part 1: Format Toy-Language Types and Function Signatures

Implement solution(kind, data) to produce the canonical printed form of a serialized Toy-Language type, in one of two modes selected by kind.

Type expressions

A type expression is one of:

• A leaf: a non-empty string such as 'int', 'float', or 'T1'.
• A tuple type: a Python list of type expressions (which may themselves be leaves or nested tuples).

A tuple type prints as its children joined by commas inside square brackets, with no spaces — and the brackets are always present, even for a single-element list.

Examples:

Input expression	Prints as
'int'	int
['int', 'T1']	[int,T1]
['T9']	[T9]
['int', ['T1', 'str']]	[int,[T1,str]]

What to implement

solution(kind, data) returns a string. kind is either 'node' or 'function'.

kind == 'node'

data is a single type expression. Format and return it using the rules above.

• A leaf returns its stored string exactly.
• A tuple returns [ + its comma-separated formatted children + ], recursing into each child.

kind == 'function'

data is a pair (parameters, output_type), where:

• parameters is a list of type expressions (the parameter types), and
• output_type is a single type expression (the return type).

Format the full signature as:

(param1,param2,...) -> returnType

• The parameter list contains the formatted parameter types joined by commas, wrapped in parentheses, with no spaces inside.
• The return type is the formatted output_type.
• The only spaces in the output are the single spaces around ->.
• A function may have zero parameters, which prints as () -> returnType.

Examples:

Input	Prints as
(['int', 'T1'], ['T1', 'str'])	(int,T1) -> [T1,str]
([], 'bool')	() -> bool

Constraints

• kind is either 'node' or 'function'.
• Each leaf is a non-empty string.
• Tuple types are represented only by Python lists.
• 0 <= number of function parameters <= 10^3.
• The total number of nodes across the input structure is at most 10^4.
• The maximum nesting depth is at most 200.

Hints

1. Use one recursive helper to format a type expression: strings return themselves, lists format each child and join with commas.
2. For a function signature, reuse the same type-formatting helper for every parameter and for the return type.

Approach

The solution canonically prints a Toy-Language type expression by mirroring the input into a small recursive tree and then serializing it.

Modeling the data with a Node tree. Every type expression is either a string leaf or a Python list (a tuple type). Node.__init__ branches on isinstance:

• a str becomes a leaf — name is set, children = None;
• a list becomes an internal node — name = None and children = [Node(c) for c in node_type], recursively wrapping each element.

This recursion naturally handles arbitrary nesting like ['int', ['T1', 'str']].

Serializing with to_str(). A leaf returns its name exactly as stored (so 'int' prints int). A tuple returns '[' + ','.join(child.to_str() ...) + ']' — bracketed, comma-separated children with no spaces, recursing into each child. This produces [int,[T1,str]].

Function signatures. When kind == 'function', data unpacks into (parameters, output_type). Function builds one Node per parameter and one for the output. to_str() joins the parameter strings with commas inside ( ) and appends ' -> ' plus the output's string. An empty parameter list [] yields '', so the output is correctly () -> returnType. The ' -> ' here is the only place spaces appear, matching the spec.

Dispatch & correctness. The top level returns Node(data).to_str() for 'node' and the Function form for 'function'; any other kind raises ValueError. Correctness follows by structural induction: leaves print themselves, and each tuple/parameter list prints exactly its children joined per the rules, so the whole structure is formatted canonically.

• Time complexity: O(N), where N is the total number of nodes across the input structure. Each node is created once during the recursive build and visited once during to_str(), and the ','.join over all children does total work proportional to the number of nodes/characters.
• Space complexity: O(N) for the mirror Node tree plus the assembled output string, with recursion depth O(D) where D is the nesting depth (at most 200), which is dominated by the O(N) tree.

Part 2: Resolve Generic Return Types in Toy-Language

Infer the concrete return type of a generic Toy-Language function call by matching its parameter patterns against the actual argument types, then substituting the inferred bindings into the declared return type.

Type expressions

A type expression is serialized in one of two ways:

• A string leaf, e.g. 'int', 'float', 'str', 'bool', or 'T1'.
• A list of type expressions, representing a tuple type, e.g. ['int', 'str'].

Two kinds of string leaves exist:

• Primitive types — lowercase strings ('int', 'str', …).
• Generic type variables — strings whose first character is uppercase ('T1', 'T2', …).

What to implement

def solution(actual_parameters, expected_parameters, output_type):
    ...

• actual_parameters — a list of type expressions giving the concrete type of each actual argument (no generics).
• expected_parameters — a list of type expressions giving the declared pattern for each parameter (may contain generics).
• output_type — a single type expression for the declared return type (may contain generics).

Return the inferred return type as a canonical string. If the call is invalid for any reason described below, return the string 'ERROR'.

Resolution rules

1. Arity. If len(actual_parameters) does not equal len(expected_parameters), the call is invalid → 'ERROR'.
2. Matching. Compare each expected parameter pattern against the corresponding actual type, position by position:
   • Expected generic → bind that generic to the actual type.
   • Expected primitive → the actual type must be the exact same primitive string.
   • Expected tuple (list) → the actual type must also be a tuple (list) of the same length, and each child is matched recursively by the same rules.
   • Any other mismatch (e.g. expected primitive vs. actual tuple, or differing tuple lengths) makes the call invalid → 'ERROR'.
3. Consistent bindings. If the same generic variable is matched more than once, every binding must be structurally identical. Otherwise the call is invalid → 'ERROR'.
4. Substitution. After all parameters match, rebuild output_type by recursively replacing every generic with its bound type, descending into tuples.
5. Unbound generics. If output_type contains a generic that was never bound during matching, the call is invalid → 'ERROR'.

Output format

Serialize the resolved return type to a canonical string:

• A primitive leaf is its own name, e.g. 'int'.
• A tuple is written as its children joined by commas inside square brackets, with no spaces, e.g. '[int,str]'. Tuples may nest, e.g. '[int,[str,bool]]'.

Examples

• solution(['int', 'str', 'int', 'int'], ['T1', 'T2', 'int', 'T1'], ['T1', 'T2']) → '[int,str]' (T1→int consistently, T2→str; the literal int parameter matches.)
• solution([['str', 'float'], ['int', 'str'], 'int'], [['T1', 'float'], 'T2', 'T3'], ['T3', 'T1']) → '[int,str]' (T1→str, T2→['int','str'], T3→int; output is [T3, T1] = [int, str].)
• solution(['int', 'str'], ['T1', 'T1'], 'T1') → 'ERROR' (T1 is bound to int then str — conflicting bindings.)
• solution([], [], 'bool') → 'bool' (No parameters; the return type is already concrete.)
• solution(['int'], ['int'], 'T1') → 'ERROR' (T1 appears in the output but was never bound.)

Constraints

• 0 <= len(actual_parameters), len(expected_parameters) <= 10^3
• Tuple types are represented only by Python lists
• Total number of nodes across all input type expressions is at most 10^4
• Maximum nesting depth is at most 200
• Primitive type names are lowercase strings
• Generic names start with an uppercase letter

Hints

1. Walk expected and actual types together recursively, building a dictionary from generic name to concrete subtree.
2. After matching the inputs, run a second recursive pass over the output type to substitute every generic.

Approach

This is a type-unification problem: match each expected parameter pattern against the actual argument type, bind generic variables, then substitute those bindings into output_type.

Helpers. is_generic(expr) flags a string whose first character is uppercase (a type variable like T1). clone deep-copies a type expression (lists nest), same tests structural equality, and format_type serializes a resolved type to the canonical string ('int' or '[int,str]').

Unification. unify(expected, actual) walks the patterns in lockstep:

• Generic expected: if already in substitutions, the new actual must structurally match the stored binding (same); otherwise bind it (storing a clone). This enforces rule 3 — repeated generics must agree.
• Primitive expected: actual must be the identical primitive string.
• Tuple (list) expected: actual must be a list of equal length, and children are unified recursively.

Any mismatch returns False.

Top level. First it checks arity (rule 1): unequal parameter counts → 'ERROR'. Then it unifies each (expected, actual) pair; any failure → 'ERROR'.

Substitution. substitute(output_type) rebuilds the output, replacing each generic with a clone of its binding and recursing into tuples. An unbound generic raises ValueError, caught to return 'ERROR' (rule 5). Finally format_type produces the canonical string.

Why correct: unification both binds first-seen generics and validates later occurrences against the stored binding, so all constraints hold simultaneously before substitution; cloning prevents aliasing between bindings and output. Tests confirm conflicting bindings (T1 = int then str) and never-bound output generics both yield 'ERROR'.

• Time complexity: O(N), where N is the total number of nodes across all parameter type expressions plus the output type. Each node is visited a constant number of times during unify/substitute (the same re-check on a repeated generic is bounded by that binding's own subtree, still O(N) overall).
• Space complexity: O(N), for the substitution table (cloned bindings), the recursion stack (bounded by nesting depth, up to ~200), and the cloned substituted output.