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

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 -> 'a.换句话说,每个都是多态值.但右手边并不是所谓的"句法价值"; 它是一个功能应用程序.(函数应用程序不允许返回多态值,因为如果是,则可以使用可变引用和列表来构造hacky函数,这将破坏类型系统;也就是说,您可以编写终止函数类型类型forall 'a 'b . 'a -> 'b.

幸运的是,在几乎所有实际情况中,所讨论的多态值都是一个函数,您可以通过eta-expansion定义它:

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
-  

那里没什么高级的!然而,价值限制适用.

在实践中,价值限制对高阶函数的定义和使用没有任何障碍 ; 你只需要扩大.

Answer 2

由于不知道值限制的详细情况，所以搜索了一下，找到了这篇文章。这是相关部分：

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

- val revlists = map rev;

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

- 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

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

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

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

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

具有相同的结果。）在文献中，用 (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 ""

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