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

Question

在Python中，我可以写

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

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

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

我收到此错误：

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

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

Answer 1

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

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

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

类型 Mu a b 被定义为包含一个函数，该函数采用 Mu a b 和 a 并生成 b。我们现在可以编写一个 fac 函数，它接受一个 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 作为参数传递给它自己。这将始终产生一个 occurs check^[1]。但是我们可以将 Mu fac 作为一个参数传递给 fac，它具有漂亮、简单的类型 Mu a a，这是一个普通函数。一层间接，你就得到了递归组合器。

您可以使用相同的 Mu 技巧来完整地编写 Y-combinator，非递归的荣耀。我强烈推荐这本身就是一项有价值的练习。

[1] 它将始终生成对函数类型的发生检查。有可能你可以用多态递归做一些真正疯狂的事情来制作一个可以接受自身（的多态变体）作为参数的函数，使用类似 printf 用于在 [=54 中获取可变参数的技巧=].这是留给 reader.

的练习

Answer 2

由于 Silvio Mayolo 已解释的原因，您不能在 Haskell 中执行此操作。但是，在 Python 中，您不需要这样做，因为您可以为函数命名并让它直接调用自身：

fac 0 = 1
fac n = n * fac (n - 1)

就像在 Python 中一样，这不一定是顶级函数：您可以在 let 绑定中定义此函数并像使用任何 lambda 一样使用它。

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

How to pass function to itself as argument in Haskell

haskell