如何在 Haskell 中将函数作为参数传递给自身

Question

在Python中，我可以写

\n

fac = lambda slf, n: 1 if n == 0 else n * slf(slf, n - 1)\nprint(fac(fac, 4))  # prints 24\n

\n

我正在尝试在 Haskell 中复制它。然而，Haskell 不会让我这样做：

\n

fac _ 0 = 1\nfac slf n = n * slf slf (n - 1)\n

\n

我收到此错误：

\n

    \xe2\x80\xa2 Occurs check: cannot construct the infinite type: t ~ t -> p -> p\n    \xe2\x80\xa2 In the first argument of \xe2\x80\x98slf\xe2\x80\x99, namely \xe2\x80\x98slf\xe2\x80\x99\n      In the second argument of \xe2\x80\x98(*)\xe2\x80\x99, namely \xe2\x80\x98slf slf (n - 1)\xe2\x80\x99\n      In the expression: n * slf slf (n - 1)\n    \xe2\x80\xa2 Relevant bindings include\n        n :: p (bound at app/Main.hs:9:10)\n        slf :: t -> p -> p (bound at app/Main.hs:9:6)\n        fac_ :: (t -> p -> p) -> p -> p (bound at app/Main.hs:8:1)\n  |\n9 | fac_ slf n = n * slf slf (n - 1)\n  |                      ^^^\n

\n

看来问题是我无法传递slf给slf. 有办法解决这个问题吗？谢谢。

\n

Answer 1

您不能直接执行此操作。Haskell 中每个术语的类型都必须能够写下来，并且如果写下来，您所提议的术语的类型将是无限长的。错误消息说了这么多：它说“我想写这个类型，但它包含它自己，所以我在炸毁你的内存之前停止了尝试”。

然而，Haskell 确实有递归类型。我们每天都以列表、树和任何其他自相似结构的形式使用它们。Haskell 永远不会允许你编写类型Either () (Int, t)，其中tis Either () (Int, t)。但事实就是如此[Int]；它只是隐藏在数据构造函数后面，因此类型的值[Int]可以无限长且自相似（列表的尾部看起来像列表），但类型仍然以漂亮、整洁、有限的形式编写[Int]。我们可以使用完全相同的技巧来获得一个可以应用于自身的函数。

newtype Mu a b = Mu { unMu :: Mu a b -> a -> b }

该类型Mu a b被定义为包含一个函数，该函数接受 aMu a b和 ana并生成 a b。我们现在可以编写一个fac以 a 作为Mu a a参数的函数。

fac :: (Num a, Eq a) => Mu a a -> a -> a
fac _ 0 = 1
fac slf n = n * unMu slf slf (n - 1)

并将其称为

fac (Mu fac) 5

所以我们永远不能将fac其作为参数传递给它本身。这总是会产生一个发生检查^[1]。但是我们可以将Mu fac，它具有很好的、简单的类型Mu a a，作为参数传递给fac，这是一个普通函数。一层间接，你就得到了递归组合器。

您可以使用同样的Mu技巧来编写完整的、非递归的Y 组合器。我强烈推荐这本身就是一项有价值的练习。

[1] 它总是会产生对函数类型的发生检查。您可能可以使用多态递归做一些真正疯狂的事情，以创建一个可以接受自身（的多态变体）作为参数的函数，使用类似于printfHaskell 中获取可变参数的技巧。这留给读者作为练习。