“价值限制”是否有效？实际上意味着没有高阶函数式编程？

Question

“值限制”实际上意味着不存在高阶函数式编程吗？

我有一个问题，每次我尝试做一点 HOP 时，我都会遇到 VR 错误。示例：

let simple (s:string)= fun rq->1 
let oops= simple ""

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)  
let oops2= get ""

我想知道这是否是 VR 特定实现的问题，或者是在不包含类型系统突变的可变类型推断语言中没有解决方案的一般问题。

Answer 1

“值限制”是否意味着不存在高阶函数式编程？

绝对不是！值限制几乎不会干扰高阶函数式编程。它的作用是在顶层限制多态函数的某些应用（而不是高阶函数）。

---

让我们看看你的例子。
您的问题是 oops 和 oops2 都是恒等函数并且具有类型 forall 'a 。 '一-> 'a.换句话说，每个都是一个多态值。但右边并不是所谓的“句法值”；它是一个函数应用程序。 （函数应用程序不允许返回多态值，因为如果是这样，您可以使用可变引用和列表构造一个黑客函数，这会颠覆类型系统；也就是说，您可以编写一个终止函数类型 type forall 'a 'b 'a -> 'b

幸运的是，在几乎所有实际情况中，所讨论的多态值都是一个函数，您可以通过 eta 扩展来定义它：

let oops x = simple "" x

这个习惯用法看起来有一些运行时成本，但取决于内联器和优化器，编译器可以消除它 - 只是糟糕的类型检查器遇到了麻烦，

oops2 示例更麻烦，因为您必须这样做 。打包和解包值构造函数：

let oops2 = F(fun x -> let F f = get "" in f x)

这相当繁琐，但匿名函数 fun x -> ... 是一个语法值，而 F 是一个数据类型构造函数，应用于语法值的构造函数也是语法值，而Bob是你的叔叔。F的打包和解包都会被编译到恒等函数中，所以。 oops2 将编译成与 oops 完全相同的机器代码。

当您希望运行时计算返回像 None 或 [] 这样的多态值时，事情会更糟糕。正如 Nathan Sanders 所暗示的，您可以使用像 rev [] 这样简单的表达式来违反值限制：

Standard ML of New Jersey v110.67 [built: Sun Oct 19 17:18:14 2008]
- val l = rev [];
stdIn:1.5-1.15 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val l = [] : ?.X1 list
-  

没有更高阶的东西！但价值限制仍然适用。

在实践中值的限制不会对高阶函数的定义和使用造成障碍；你只需进行 eta 扩展即可。

Answer 2

我不知道值限制的详细信息，所以我搜索并找到 这篇文章。这是相关部分：

显然，我们不会在程序中编写表达式 rev []，因此它不是多态的并不特别重要。但是如果我们使用函数调用创建一个函数怎么办？对于柯里化函数，我们一直这样做：

- val revlists = 地图 rev;

这里的修订列表应该是多态的，但值限制让我们陷入困境：

- val revlists = 地图 rev;
stdIn:32.1-32.23 警告：类型变量未泛化，因为
   值限制被实例化为虚拟类型（X1，X2，...）
val revlists = fn : ?.X1 列表列表 -> ?.X1列表列表

幸运的是，我们可以使用一个简单的技巧来使修订列表具有多态性。我们可以将 revlists 的定义替换为

- val revlists = (fn xs => 地图 rev xs);
val revlists = fn : '列表列表 -> '一个列表列表

现在一切正常，因为 (fn xs => map rev xs) 是一个语法值。
（同样，我们可以使用更常见的 fun 语法：

- 有趣的 revlists xs = 地图 rev xs;
val revlists = fn : '列表列表 -> '一个列表列表

具有相同的结果。）在文献中，用 (fn x => ex) 替换函数值表达式 e 的技巧称为 eta 扩展。经验发现，eta 扩展通常足以处理值限制。

总而言之，高阶编程似乎不像无点编程那样受到限制。这也许可以解释我在将 Haskell 代码转换为 F# 时遇到的一些问题。

---

编辑：具体来说，这里是如何修复第一个示例：

let simple (s:string)= fun rq->1 
let oops= (fun x -> simple "" x)     (* eta-expand oops *)

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)
let oops2= get ""

我还没有弄清楚第二个示例，因为类型构造函数妨碍了。

Answer 3

这是这个问题的答案< /a> 在 F# 上下文中。
总而言之，在 F# 中，将类型参数传递给泛型（=多态）函数是一个运行时操作，因此它实际上是类型安全的泛化（例如，您不会在运行时崩溃）。然而，如此普遍化的价值行为可能会令人惊讶。

对于 F# 中的这个特定示例，可以使用类型注释和显式类型参数来恢复泛化：

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)  
let oops2<'T> : 'T SimpleType = get ""