Toy language type inference with generics and tuples

A small typed language has three kinds of type:

• Primitives: int, float, char.
• Generics: placeholders named T followed by a number (T1, T2, ...). A generic can stand for any type, including a tuple.
• Tuples: an ordered list of types, which may be nested, e.g. [int,[T1,char]].

A function has a list of parameter types and a single return type.

Types are given to you already built as objects. You do not need to parse strings. Model a type as a Node (a named leaf, or a tuple with child nodes) and a function as Function(params, ret).

Part 1: printing

Implement to_str() for both classes:

• A primitive or generic prints its name.
• A tuple prints its elements comma-separated inside square brackets, with no spaces: [int,[T1,char]].
• A function prints its parameters comma-separated inside parentheses, then ->, then the return type: (int,[T1,float]) -> T1.

Part 2: return type inference

Implement infer_return(fn, args). args is a list of concrete argument types, one for each parameter. Return the function's return type with every generic replaced by the type it must stand for. Raise an error when:

• the number of arguments differs from the number of parameters;
• a primitive parameter receives a different type;
• a tuple parameter receives a non-tuple, or a tuple of a different length;
• one generic would have to stand for two different types;
• the return type uses a generic that no parameter binds.

Examples

Function (T1, [T1,T2]) -> [T2,T1] called with (float, [float,[int,int]]): T1 binds to float and T2 binds to [int,int], so the result is [[int,int],float].

Function (T1, T1) -> T1 called with (int, char) raises an error, because T1 cannot be both int and char.