SML中的递归匿名函数

Question

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

我已经写了一个例子来说明我想要的：

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

- dbmikus

---

我不是机器学习专家，但你可能正在寻找一个包含固定点组合子（如Y组合子）的东西，这是一种通常的方式，可以通过匿名函数构建递归函数。 - templatetypedef

@templatetypedef 你是正确的，只要你想使用匿名函数（请记住原问题并没有使用匿名函数），但这不是一种漂亮的做法。请参考我的答案最后部分的示例 :) - Jesper.Reenberg

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)

我认为只有一个使用长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的阶乘，该代码使用匿名函数表达式表示faculty函数，然后将计算结果绑定到res。

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

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

---

对George Kangas答案的更新回应：

在我所知道的语言中，递归函数总会被绑定到一个名称上。方便和常规的方式是通过像“define”、“let”或“letrec”这样的关键字提供的。

显然是根据定义而言的。如果（无论是否递归）函数未绑定到名称上，则它将是匿名的。

非传统的、更具匿名性的方式是通过lambda绑定实现的。

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

Jesper Reenberg的答案展示了 lambda 绑定；“匿名”函数通过 lambdas ( 在 SML 中称为 "fn" )绑定到"f"和"fact"这两个名称上。

这个匿名函数实际上是匿名的（不是“匿名”——没有引号），当然它将在作为参数传递给其他函数时被绑定在作用域中。否则，该语言将完全无用。当调用map (fn x => x) [.....]时，发生的正是同样的事情，在这种情况下，匿名身份函数仍然是匿名的。

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

对于我的示例来说，这实际上是正确的，通过在只包含fun Y ...和val res ..的文件上使用mlton并带上-show-basis参数即可看到。

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中是否可能编写递归匿名函数？

简单的答案是可以。复杂的答案是（包括其他内容）使用不动点组合子的示例，而不是在另一种语言中使用甚至在SML中也无法实现的功能编写的“lambdanonymous”示例。

- Jesper.Reenberg

---

"[...] since val rec is just the derived form of fun [...]"：难道不是相反吗？ - Hibou57

不是的。也许我们指的是同一件事，但是从两个不同的角度来看待它。val rec 是核心语言的一部分，而 fun 关键字则是派生形式。我手头没有定义，但请参见 [http://homepages.inf.ed.ac.uk/stg/NOTES/notes.pdf] 的第 3.4 节（这是我在谷歌上找到的最好的资料）。 - Jesper.Reenberg

Answer 2

您只需在 val 后面加上 rec，例如：

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

维基百科 在第一节的开头进行了描述。

- murgatroid99

---

明白了。我想维基百科上没有那个信息，所以我到处找了一下。谢谢。 - dbmikus

非常感谢！ :) 你是真正的救星！ :) - Horse SMith

Answer 3

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

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

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

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

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

- Peng Wang

Answer 4

在我所知道的语言中，递归函数总是会被绑定到一个名称上。方便和常规的方式是通过关键字如“define”、“let”或“letrec”等提供的。

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

一个更短的“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。

- George Kangas

---

你看了这段代码吗？用OCaml示例回答原问题并没有带来价值，特别是在使用SML没有的递归类型时。总之，我不认为你的帖子有什么意义，除了陈述一些已知的事实。请查看我的更新帖子。 - Jesper.Reenberg