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 中所示，因为 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

，然后您可以使用下面的代码计算事实 5，该代码使用匿名
函数来表达功能函数，然后绑定结果
计算到res。

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

定点代码和示例计算由 Morten Brøns-Pedersen 提供。

---

对乔治·坎加斯的回答的更新回复：

在我所知道的语言中，递归函数总是会绑定到
姓名。方便且常规的方式是通过关键字提供的，例如
“定义”，或“让”，或“letrec”，...

根据定义，这很简单。如果函数（无论是否递归）未绑定到名称，它将是匿名的。

非常规、更匿名的方式是通过 lambda 绑定。

我不明白匿名函数有什么非常规之处，它们一直在 SML 中使用，事实上在任何函数式语言中都是如此。它甚至开始出现在越来越多的命令式语言中。

Jesper Reenberg 的回答显示了 lambda 绑定； “匿名者”
函数通过 lambda 绑定到名称“f”和“fact”（称为
SML 中的“fn”）。

匿名函数实际上是匿名的（不是“匿名”——没有引号），是的，它当然会被绑定在它作为参数传递的函数的范围中。在任何其他情况下，语言将完全没有用处。调用 map (fn x => x) [.....] 时会发生完全相同的事情，在本例中是匿名身份函数，实际上仍然是匿名的。

匿名函数的“正常”定义（至少根据 维基百科），表示它不能绑定到标识符有点弱，应该包含“在当前环境中”的隐式声明。

对于我的示例来说，这实际上是正确的，正如通过在仅包含 fun Y ... 和 val res ..< 的文件上使用 -show-basis 参数在 mlton 中运行它所看到的那样。 /code>

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

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

更短的“lambdanonymous”替代方案，需要启动 OCaml
通过“ocaml -rectypes”：

（有趣的 fn -> ffn） 
(fun fn -> if n = 0 then 1 else n * (ff (n - 1))
7;;产生 7! = 5040。

看来您完全误解了原始问题的想法：

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

简单的答案是肯定的。复杂的答案是（除其他外？）使用定点组合器完成的示例，而不是使用另一种语言完成的“匿名”（无论这是什么意思）示例，使用 SML 中根本不可能实现的功能。

Answer 2

您所要做的就是将 rec 放在 val 之后，如

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

Wikipedia 在第一部分顶部附近对此进行了描述。

Answer 3

let fun fact 0 = 1
      | fact x = x * fact (x - 1)
in
  fact
end

这是一个递归匿名函数。名称“fact”仅在内部使用。

某些语言（例如 Coq）使用“fix”作为递归函数的原语，而某些语言（例如 SML）使用 recursive-let 作为原语。这两个原语可以相互编码：

fix f => e   
  := let rec f = e in f end

let rec f = e ... in ... end 
  := let f = fix f => e ... in ... end 

Answer 4

在我所知道的语言中，递归函数总是与名称绑定。方便且传统的方式是通过诸如“define”、“let”或“letrec”之类的关键字提供的。

非常规、更加匿名的方式是通过 lambda 绑定。 Jesper Reenberg 的答案显示了 lambda 结合； “匿名”函数通过 lambda 绑定到名称“f”和“fact”（在 SML 中称为“fn”）。

更短的“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;;

产生 7！ = 5040。