Toy Language Generic Return-Type Inference

A toy type language contains:

• primitive types char, int, and float;
• generic names made from an uppercase letter followed by digits, such as T1 and T2;
• tuple types such as [int, T1, char], which may contain nested tuples;
• function signatures such as [int; [int, T1]; T2] -> [char, T2, [float, float]].

Given a function signature and concrete actual parameter types, infer the concrete return type.

Match formal and actual parameter types recursively:

• A primitive formal type must equal the corresponding actual type.
• A tuple must match a tuple with the same number of elements, and corresponding elements must match recursively.
• The first occurrence of a generic binds it to the corresponding concrete actual type.
• Every later occurrence of that generic must match the same bound type.

After all parameters match, substitute the generic bindings into the return type. A fixed-type mismatch, tuple-shape mismatch, or conflicting generic binding is an error.

The outer formal-parameter list may use commas or semicolons. Return the inferred type in canonical form with comma-and-space separators inside tuples.

What the interview report shared

The onsite exercise provided Node and Function classes for the same primitive, generic, tuple, and function grammar. Its second part asked candidates to infer a return Node by substituting generic bindings and rejecting mismatches or conflicts. The report also supplied the complete valid example below. This practice function accepts the report's textual type notation directly.