functional-programming - "Value Restriction"实际上意味着没有高阶函数式编程吗？

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

Does “Value Restriction” mean that there is no higher order functional programming?

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

<小时/>

让我们看一下您的示例。你的问题是oops和oops2都是恒等函数并且类型为 forall 'a . '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
-  

没有什么更高阶的东西了!但值(value)限制仍然适用。

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