nsa*_*llo 91 recursion f# ocaml
为什么F#中的函数和Ocaml(可能还有其他语言)默认不是递归的？
换句话说,为什么语言设计者决定明确地让你输入如下rec声明是一个好主意:
let rec foo ... = ...
并且默认情况下不提供函数递归功能？为什么需要显式rec构造？
Jon*_*rop 83
最初的ML的法国和英国后裔做出了不同的选择,他们的选择在几十年中一直被继承到现代变体.所以这只是遗产,但确实会影响这些语言中的习语.
默认情况下,法语CAML系列语言(包括OCaml)中的函数不是递归的.这种选择使得let在这些语言中使用函数(和变量)定义变得容易,因为您可以在新定义的主体内引用先前的定义.F#从OCaml继承了这种语法.
例如,p在计算OCaml中序列的Shannon熵时取代函数:
let shannon fold p =
let p x = p x *. log(p x) /. log 2.0 in
let p t x = t +. p x in
-. fold p 0.0
注意p高阶shannon函数的参数如何在p正文的第一行中被另一个函数取代,然后p在正文的第二行中被另一个函数取代.
相反,ML系列语言的英国SML分支采用了另一种选择,fun默认情况下SML的绑定函数是递归的.当大多数函数定义不需要访问其函数名的先前绑定时,这会产生更简单的代码.然而,所取代的功能是由使用不同的名称(f1,f2等),污染范围并有可能意外地调用函数的错"版本".现在隐式递归fun绑定函数和非递归val绑定函数之间存在差异.
Haskell可以通过将定义限制为纯粹来推断定义之间的依赖关系.这使得玩具样本看起来更简单,但其他地方的成本却很高.
请注意,Ganesh和Eddie给出的答案是红色鲱鱼.他们解释了为什么函数组不能放在巨型函数中,let rec ... and ...因为它会影响类型变量的泛化.这与recSML中的默认值无关,而与OCaml 无关.
GS *_*ica 51
明确使用的一个关键原因rec是与Hindley-Milner类型推断有关,它是所有静态类型函数式编程语言的基础(虽然以各种方式改变和扩展).
如果您有一个定义let f x = x,那么您希望它具有类型'a -> 'a并适用于不同'a类型的不同类型.但同样地,如果你写作let g x = (x + 1) + ...,你会期望x被视为int在其余部分g.
Hindley-Milner推理处理这种区别的方式是通过明确的泛化步骤.在处理程序时的某些时刻,类型系统会停止并说"好了,这些定义的类型将在此时推广,这样当有人使用它们时,其类型中的任何自由类型变量都将被新实例化,因此不会干扰这个定义的任何其他用途."
事实证明,进行这种泛化的合理位置是在检查相互递归的函数集之后.任何更早的,你会概括太多,导致类型实际上可能发生碰撞的情况.任何以后,你会概括太少,使得定义不能用于多种类型的实例化.
因此,鉴于类型检查器需要知道哪些定义集是相互递归的,它能做什么？一种可能性是简单地对范围中的所有定义进行依赖性分析,并将它们重新排序到最小的可能组中.Haskell实际上是这样做的,但是在F#(和OCaml和SML)等具有无限制副作用的语言中,这是一个坏主意,因为它可能会重新排序副作用.因此,它要求用户明确标记哪些定义是相互递归的,因此通过扩展来进行泛化.
zrr*_*zrr 10
这是一个好主意有两个关键原因:
首先,如果启用递归定义,则不能引用先前对同名值的绑定.当您执行扩展现有模块之类的操作时,这通常是一个有用的习惯用法.
其次,递归值,尤其是相互递归值的集合,更难以推理,然后定义按顺序进行,每个新定义都建立在已经定义的基础之上.在阅读此类代码时,可以保证除了明确标记为递归的定义之外,新定义只能引用先前的定义.
一些猜测：
let不仅用于绑定函数，还用于绑定其他常规值。大多数形式的值都不允许递归。某些形式的递归值是允许的（例如函数、惰性表达式等），因此它需要一个明确的语法来表明这一点。let构造类似于letLisp 和 Scheme 中的构造；这是非递归的。letrecScheme中有一个单独的构造用于递归让我们