5

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

我有一个问题，每次我尝试做一些 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 的特定实现的问题，还是在类型系统中不包含突变的可变类型推断语言中没有解决方案的一般问题。

4

3 回答 3

6

“价值限制”是否意味着没有更高阶的函数式编程？

绝对不！ 值限制几乎不会干扰高阶函数式编程。它所做的是将多态函数的一些应用程序——而不是高阶函数——限制在顶层。

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

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

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

当您希望运行时计算返回像Noneor之类的多态值时，情况会更加糟糕[]。正如 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-expand。

于 2010-04-16T01:50:05.273 回答
2

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

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

type 'a SimpleType= F of (int ->'a-> 'a)
let get a = F(fun req -> id)  
let oops2<'T> : 'T SimpleType = get ""
于 2010-05-06T04:19:24.843 回答
2

不知道限价的具体内容，于是搜了一下，找到了这篇文章。以下是相关部分：

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

- val revlists = map rev;

这里的 revlists 应该是多态的，但是值限制让我们感到困惑：

- val revlists = map rev;
stdIn:32.1-32.23 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val revlists = fn : ?.X1 list list -> ?.X1 list list

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

- val revlists = (fn xs => map rev xs);
val revlists = fn : 'a list list -> 'a list list

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

- fun revlists xs = map rev xs;
val revlists = fn : 'a list list -> 'a list list

结果相同。）在文献中，将函数值表达式 e 替换为 (fn x => ex) 的技巧称为 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 ""

我还没有想出第二个，因为类型构造函数妨碍了。

于 2010-04-15T12:57:00.090 回答