类型推断的统一问题

Question

有没有人的想法如何类型推理问题

E > hd (cons 1 nil) : α0

与定型环境

                E={
                   hd : list(α1 ) → α1 ,
                   cons : α2 → list(α2 ) → list(α2 ),
                   nil : list(α3 ),
                   1 : int
                }

可以在统一的问题被转移

任何帮助将真正理解！

Answer 1

首先，重命名的类型变量，以使没有在表达式中的变量与在打字环境变量碰撞。 （在您的例子，这是因为已经表达的引用{A0}完成，和打字环境引用{A1，A2，A3}。

其次，使用新型的变量，为您的表达中的每个子表达式类型变量，从而产生这样的：

nil : a4
1 : a5
cons : a6
(cons 1 nil) : a7
hd : a8
hd (cons 1 nil) : a0 // already had a type variable

第三，产生一组必须保持型变量之间的方程。您可以从下往上做到这一点，从上而下，或者以其他方式。请参见麒麟大厦，巴斯蒂安。顶级品质类型的错误消息。 2005年了解为什么你可能想选择一个这样或那样的大量具体的细节。这将导致这样的：

a4 = list(a3) // = E(nil)
a5 = int // = E(1)
a6 = a2 -> list(a2) -> list(a2) // = E(cons)

// now it gets tricky, since we need to deal with application for the first time
a5 = a2 // first actual param of cons matches first formal param of cons
a4 = list(a2) // second actual param of cons matches type of second formal param of cons
a7 = list(a2) // result of (cons 1 nil) matches result type of cons with 2 params

a8 = list(a1) -> a1 // = E(hd)    

// now the application of hd
a7 = list(a1) // first actual param of hd matches type of first formal param of hd
a0 = a1 // result of hd (cons 1 nil) matches result type of hd with 1 param

请注意小心，如果从类型环境中使用两次相同的功能，我们需要更多新的类型变量（在第二步中，以上）与统一，这样就利弊使用，我们不会意外拨打所有电话同一类型。我不知道如何才能更清楚地解释这一部分，对不起。在这里，我们是在容易的情况下，因为HD和缺点各自只使用一次。

四，统一这些方程，产生（如果我没有犯了一个错误）是这样的：

a4 = list(int)
a5 = int
a6 = int -> list(int) -> list(int)
a7 = list(int)
a8 = list(int) -> int
a0 = int

飘柔，你现在知道每个子表达式在你的原始表达式类型。

（公平的警告，我有点一个业余的自己在这些问题上，我可能已经取得了印刷错误或无意欺骗这里的某个地方。）