SML中的递归匿名函数

Question

是否可以在SML中编写递归匿名函数？我知道我可以使用fun语法,但我很好奇.

我写过,作为我想要的一个例子:

val fact =
    fn n => case n of
                 0 => 1
               | x => x * fact (n - 1)

Answer 1

将它绑定到变量时,匿名函数不再是匿名函数.而且,由于除了外观之外没有区别val rec的派生形式fun,你也可以使用fun语法编写它.你也可以做的模式匹配fn表达式以及在case,因为病例都源于fn.

所以简单来说,你可以把你的功能写成

val rec fact = fn 0 => 1
                | x => x * fact (x - 1)

但这与下面的内容完全相同(在我看来)

fun fact 0 = 1
  | fact x = x * fact (x - 1)

据我所知,使用long编写代码只有一个原因val rec,那就是因为您可以使用注释和强制类型更轻松地注释代码.例如,如果您之前已经看过Haskell代码并且喜欢它们键入注释函数的方式,那么您可以编写类似这样的内容

val rec fact : int -> int =
fn 0 => 1
 | x => x * fact (x - 1)

正如提到的templatetypedef,可以使用定点组合器来完成它.这样的组合器可能看起来像

fun Y f =
    let
      exception BlackHole
      val r = ref (fn _ => raise BlackHole)
      fun a x = !r x
      fun ta f = (r := f ; f)
    in
      ta (f a)
    end

然后你可以fact 5用下面的代码计算,它使用匿名函数来表达教师函数,然后将计算结果绑定到res.

val res =
    Y (fn fact =>
       fn 0 => 1
        | n => n * fact (n - 1)
      )
      5                       

定点代码和示例计算由MortenBrøns-Pedersen提供.

对George Kangas回答的更新回复:

在我所知的语言中,递归函数将始终绑定到名称.方便和传统的方式由关键字提供,如"定义",或"让",或"letrec",...

根据定义,这是真实的.如果函数(递归与否)未绑定到名称,则它将是匿名的.

非传统的,更匿名的方式是通过lambda绑定.

我没有看到匿名函数有什么非常规的,它们一直在SML中使用,实际上是在任何函数式语言中.它甚至开始出现在越来越多的命令式语言中.

Jesper Reenberg的答案显示了lambda绑定; "匿名"函数通过lambdas绑定到名称"f"和"fact"(在SML中称为"fn").

匿名函数实际上是匿名的(不是"匿名" - 没有引号),是的当然它将被绑定在作为参数传递的函数的范围内.在任何其他情况下,语言将完全无用.完全相同的事情发生在调用map (fn x => x) [.....],在这种情况下匿名身份函数,实际上仍然是匿名的.

匿名函数的"正常"定义(至少根据维基百科),说它不能绑定到标识符,有点弱,应该包括"在当前环境中"的隐式语句.

事实上这对我的例子来说是正确的,正如在mlton中使用-show-basis参数在仅包含fun Y ...和val res ..

val Y: (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
val res: int32

由此可以看出,没有任何匿名函数在环境中绑定.

一个较短的"lambdanonymous"替代方案,需要通过"ocaml -rectypes"启动OCaml:

(fun f n -> f f n) 
(fun f n -> if n = 0 then 1 else n * (f f (n - 1))
7;; Which produces 7! = 5040.

您似乎完全误解了原始问题的想法:

是否可以在SML中编写递归匿名函数？

简单的答案是肯定的.复杂的答案是(除其他外？)使用定点组合器完成此操作的一个例子,而不是"lambdanonymous"(这应该是什么意思)的示例在另一种语言中使用SML中甚至远程可能的功能完成.

Answer 2

所有你需要做的就是把它放在rec后面val,如同

val rec fact =
        fn n => case n of
                     0 => 1
                   | x => x * fact (n - 1)

维基百科在第一部分的顶部描述了这一点.