Haskell函数是高阶的当且仅当它的类型有多个箭头？

Question

一位教授在我所参加的一堂课上讲课，他声称：

在检查其类型时，高阶函数只能有一个箭头.

我不同意这一说法，我试图证明这是错误的。我试着设置一些函数，但是后来我发现我的函数可能不是高阶函数。以下是我所拥有的：

f x y z = x + y + z
f :: a -> a->  a -> a

g = f 3
g :: a -> a -> a

h = g 5
h :: a -> a

最后，我认为我的证明是错误的，但我仍然不相信高阶函数在检查类型时只能有一个以上的箭头。

那么，是否有任何资源或可能有人可以证明高阶函数可能只有一个箭头？

Answer 1

严格地说，这个说法是正确的。这是因为这里摘自维基百科的“高阶函数”一词的通常定义是执行以下一项或两项任务的函数：

• 将函数作为参数，或
• 返回函数作为其结果。

很明显，没有任何函数的类型签名中有一个箭头可以是高阶函数，因为在签名a -> b中，在箭头的两边没有创建某种形式x -> y的“空间”--只是没有足够的箭头。

(这个论点实际上有一个很大的缺陷，你可能注意到了，我将在下面加以说明。但你的教授的意思可能是“精神上的”。)

严格地说，这句话在Haskell中也是正确的--尽管在大多数其他语言中并非如此。Haskell在这里的显著特点是功能被匆忙化了。例如，像(+)这样的函数，其签名是：

a -> a -> a

(我将忽略一个Num a约束，因为如果我们要计算“箭头”，它只会混淆问题)，通常被认为是两个参数的函数:它需要2个a，并生成另一个a。在大多数语言中，当然所有语言都有一个错误的函数/运算符，这永远不会被描述为高阶函数。但是在Haskell中，由于函数是匆匆的，上面的签名实际上只是括号版本的缩写：

a -> (a -> a)

这显然是一个高阶函数。它接受一个a并生成一个a -> a类型的函数。(从上面回想起，返回函数是HOF的特征之一。)在Haskell，正如我所说，这两个签名是一回事。(+)确实是一个高阶函数--我们只是经常没有注意到，因为我们打算给它两个参数，我们实际上是指给它一个参数，得到一个函数，然后再给那个函数第二个参数。由于Haskell为参数应用函数提供了方便、无括号的语法，所以没有任何区别。(这再次与非函数式语言形成对比:添加的“函数”总是有两个参数，只有一个参数通常是错误的。如果语言具有一流的函数，那么您确实可以定义咖喱形式，例如在Python中：

def curried_add(x):
    return lambda y: x + y

但是，这显然是一个与通常使用的两个参数的直接函数不同的函数，并且通常不太方便应用，因为需要将其称为curried_add(x)(y)而不是add(x,y)。

因此，如果我们考虑到这一点，你的教授的说法是完全正确的。

嗯，除了下面的例外，我在上面提到过。我一直在假设有表格签名的东西

a -> b

不是HOF*。如果a或b是一个函数，这当然不适用。通常，该函数的类型将包含一个箭头，我们在这里默认地假设a或b都不包含箭头。嗯，Haskell有类型的同义词，所以我们可以很容易地定义，比如说：

type MyFunctionType = Int -> Int

然后，带有签名MyFunctionType -> a或a -> MyFunctionType的函数无疑是HOF函数，尽管只要看一眼签名，它就不“像HOF了”。

*这里要说明的是，a和b指的是尚未指定的特定类型--我指的不是实际的签名a -> b，它意味着适用于任何类型的a和b的多态函数，它们不一定是函数。

Answer 2

你的功能是更高级的。实际上，以您的功能为例：

f :: a -> a -> a -> a
f x y z = x + y + z

这是一种不那么冗长的形式：

f :: a -> (a -> (a -> a))

因此，它是一个接受a并返回函数的函数。高阶函数是(a)以函数作为参数，或(b)返回函数的函数。同时两者都可以是真实的。在这里，函数f返回一个函数。

因此，函数的类型总是a -> b，a是输入类型，b是返回类型。如果a有一个箭头(如(c -> d) -> b)，那么它就是一个高阶函数，因为它接受一个函数作为参数。

如果b有一个箭头，比如a -> (c -> d)，那么这也是一个高阶函数，因为它返回一个函数。

Answer 3

是的，由于Haskell函数总是被匆匆处理，所以我可以给出高阶函数的最小示例和示例：

1)至少将函数作为参数的函数，例如：

apply :: (a -> b) -> a -> b
apply f x = f x

( 2)至少有3项论点：

sum3 :: Int -> Int -> Int
sum3 a b c = a + b + c

因此，这可以理解为：

sum3 :: Int -> (Int -> Int)