Hindley-Milner 中的“让”推理
`Let` inference in Hindley-Milner
我正在尝试通过用我常用的语言 Clojure 实现算法 W 来自学 Hindley-Milner 类型推断。我 运行 遇到了 let 推理的问题，我不确定我是否做错了什么，或者我期望的结果是否需要算法之外的东西。
基本上，使用 Haskell 表示法，如果我尝试推断其类型：
\a -> let b = a in b + 1
我明白了：
Num a => t -> a
但我应该得到这个：
Num a => a -> a
同样，我实际上是在 Clojure 中这样做的，但我不认为问题是 Clojure 特有的，所以我使用 Haskell 符号来使其更清楚。当我在 Haskell 中尝试时，我得到了预期的结果。
无论如何，我可以通过将每个 let 转换为函数应用程序来解决该特定问题，例如：
\a -> (\b -> b + 1) a
但后来我失去了 let 多态性。由于我对 HM 没有任何先验知识，我的问题是我是否遗漏了一些东西，或者这是否只是算法的工作方式。
编辑
如果有人遇到类似问题并且想知道我是如何解决它的，我正在关注 Algorith W Step By Step。在第 2 页的底部，它说 "It will occasionally be useful to extend the Types methods to lists." 因为它对我来说不是强制性的，所以我决定跳过那部分，稍后再看。
然后我将 TypeEnv 的 ftv 函数直接翻译成 Clojure，如下所示：(ftv (vals env))。由于我将 ftv 实现为 cond 形式并且没有 seq 的子句，它只是为 (vals env) 返回 nil。这当然正是静态类型系统旨在捕获的那种错误！无论如何，我只是将 ftv 中与 env 映射相关的子句重新定义为 (reduce set/union #{} (map ftv (vals env))) 并且它有效。
很难说出哪里出了问题，但我猜你的 let-generalization 是错误的。
让我们手动输入字词。
\a -> let b = a in b + 1
首先，我们将 a 与一个新类型变量相关联，比如 a :: t0。
然后我们输入b = a。我们也得到 b :: t0。
然而，这是关键点，我们应该不将b的类型概括为b :: forall t0. t0。这是因为我们只能对环境中不存在的 tyvar 进行概括：在这里，相反，我们在环境中确实有 t0，因为 a :: t0 在那里。
如果您对它进行概括，您会得到一种对于 b 而言过于笼统的类型。然后 b+1 变为 b+1 :: forall t0. Num t0 => t0，整个术语变为 forall t0 t1. Num t1 => t0 -> t1，因为 a 和 b 的类型不相关（t0，一旦泛化，可以 alpha 转换为 t1).
我正在尝试通过用我常用的语言 Clojure 实现算法 W 来自学 Hindley-Milner 类型推断。我 运行 遇到了 let 推理的问题，我不确定我是否做错了什么，或者我期望的结果是否需要算法之外的东西。
基本上，使用 Haskell 表示法，如果我尝试推断其类型：
\a -> let b = a in b + 1
我明白了：
Num a => t -> a
但我应该得到这个：
Num a => a -> a
同样，我实际上是在 Clojure 中这样做的，但我不认为问题是 Clojure 特有的，所以我使用 Haskell 符号来使其更清楚。当我在 Haskell 中尝试时，我得到了预期的结果。
无论如何，我可以通过将每个 let 转换为函数应用程序来解决该特定问题，例如：
\a -> (\b -> b + 1) a
但后来我失去了 let 多态性。由于我对 HM 没有任何先验知识，我的问题是我是否遗漏了一些东西，或者这是否只是算法的工作方式。
编辑
如果有人遇到类似问题并且想知道我是如何解决它的，我正在关注 Algorith W Step By Step。在第 2 页的底部，它说 "It will occasionally be useful to extend the Types methods to lists." 因为它对我来说不是强制性的，所以我决定跳过那部分，稍后再看。
然后我将 TypeEnv 的 ftv 函数直接翻译成 Clojure，如下所示：(ftv (vals env))。由于我将 ftv 实现为 cond 形式并且没有 seq 的子句，它只是为 (vals env) 返回 nil。这当然正是静态类型系统旨在捕获的那种错误！无论如何，我只是将 ftv 中与 env 映射相关的子句重新定义为 (reduce set/union #{} (map ftv (vals env))) 并且它有效。
很难说出哪里出了问题，但我猜你的 let-generalization 是错误的。
让我们手动输入字词。
\a -> let b = a in b + 1
首先，我们将 a 与一个新类型变量相关联，比如 a :: t0。
然后我们输入b = a。我们也得到 b :: t0。
然而，这是关键点，我们应该不将b的类型概括为b :: forall t0. t0。这是因为我们只能对环境中不存在的 tyvar 进行概括：在这里，相反，我们在环境中确实有 t0，因为 a :: t0 在那里。
如果您对它进行概括，您会得到一种对于 b 而言过于笼统的类型。然后 b+1 变为 b+1 :: forall t0. Num t0 => t0，整个术语变为 forall t0 t1. Num t1 => t0 -> t1，因为 a 和 b 的类型不相关（t0，一旦泛化，可以 alpha 转换为 t1).