Toy Language：Node、Function序列化与嵌套泛型推断

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• primitive为小写名字，泛型为大写字母后接数字，tuple由Node列表构成，允许嵌套；实际调用参数必须具体化。
• Function文本采用(param1,param2) -> return，tuple文本方括号无空格；返回泛型未被参数绑定时报错，不默认任意类型。

解题路线

1. 第一部分Node叶直接输出名字，tuple递归join，Function将参数与返回分开。类型对象表达结构，不把复杂tuple当不可分析字符串。
2. 推断时共享一个bindings表。primitive要求精确同类型；tuple要求同长度并逐位匹配；generic首次绑定完整actual Node，后续出现须结构相同，因此T1可绑定嵌套tuple。
3. 输出替换必须递归。不要修改Function模板，否则第一次调用绑定int会污染下一次str调用；保持Node不可变合同，结果可以共享不可变绑定节点。参数个数、tuple形状、primitive、generic冲突分开检测。

手动走一遍

([T1,float],T2,T3) -> [T3,T1]，args=[str,float]/[int,str]/int，得到[int,str]。(T1,T1)传int/str冲突；(T1) -> T2的T2未绑定，不能猜成T1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

import re
class Node:
    def __init__(self,value):
        if type(value) is str:
            if not re.fullmatch(r"[a-z]+|[A-Z][0-9]+",value):raise ValueError("type name")
            self.value=value
        elif type(value) is list and all(isinstance(x,Node) for x in value):self.value=tuple(value)
        else:raise ValueError("leaf name or child nodes required")
    def to_str(self):return self.value if isinstance(self.value,str) else '['+','.join(x.to_str() for x in self.value)+']'
    def __eq__(self,other):return isinstance(other,Node) and self.value==other.value
class Function:
    def __init__(self,parameters,output):self.parameters=tuple(parameters);self.output=output
    def to_str(self):return '('+','.join(x.to_str() for x in self.parameters)+') -> '+self.output.to_str()

def generic(node):return isinstance(node.value,str) and bool(re.fullmatch(r"[A-Z][0-9]+",node.value))
def infer(arguments,function):
    if len(arguments)!=len(function.parameters):raise ValueError("arity")
    bindings={}
    def concrete(node):
        if generic(node):return False
        return isinstance(node.value,str) or all(concrete(x) for x in node.value)
    if not all(concrete(x) for x in arguments):raise ValueError("actual arguments must be concrete")
    def match(expected,actual):
        if generic(expected):
            key=expected.value
            if key in bindings and bindings[key]!=actual:raise ValueError("generic conflict")
            bindings[key]=actual;return
        if isinstance(expected.value,str):
            if expected!=actual:raise ValueError("primitive mismatch")
        else:
            if isinstance(actual.value,str) or len(expected.value)!=len(actual.value):raise ValueError("tuple shape")
            for x,y in zip(expected.value,actual.value):match(x,y)
    for expected,actual in zip(function.parameters,arguments):match(expected,actual)
    def substitute(node):
        if generic(node):
            if node.value not in bindings:raise ValueError("unbound return generic")
            return bindings[node.value]
        if isinstance(node.value,str):return Node(node.value)
        return Node([substitute(x) for x in node.value])
    return substitute(function.output)

复杂度

输入及实际类型树总节点N、输出展开节点R；递归匹配含重复泛型结构比较，可达O(N+重复绑定比较量)，输出O(R)，字符串分层拼接保守O(hR)。存绑定O(泛型数+所引用树)，栈O(h)。

易错点与追问

容易失分的边界

• 只比较tuple的外层节点类型会漏内部冲突。
• 将大写名字都当generic会错误接纳未定义语法。

继续深挖

• 允许actual含泛型时如何变成双侧unification并加occurs check？
• 字符串解析器作为新要求时，怎样处理括号/分隔符与错误位置？