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

Question

一位教授我正在类的类(class)的教授声称以下内容。

A higher-order function could have only one arrow when checking its type.

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

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

严格来说，这个说法是正确的。这是因为术语“高阶函数”的通常定义取自Wikipedia。 , 是执行以下一项或两项操作的函数:

将函数作为参数，或

返回一个函数作为结果

很明显，在其类型签名中没有单个箭头的函数可以是高阶函数，因为在签名 a -> b ，没有“空间”来创建 x -> y 形式的东西在箭头的任一侧 - 根本没有足够的箭头。

(这个论点实际上有一个重大缺陷，你可能已经发现了，我将在下面说明。但对于你教授的意思来说，这可能是“精神上”的。)

相反，严格来说，在 Haskell 中也是如此——尽管在大多数其他语言中都不是。 Haskell 的显着特点是函数是柯里化(Currying)的。例如，像 (+) 这样的函数，其签名为:

a -> a -> a

(我将忽略 Num a 约束，因为如果我们应该计算“箭头”，它可能只会混淆问题)，通常被认为是两个参数的函数:它需要 2 a s 并产生另一个 a .在大多数语言中，当然都有类似的函数/运算符，这永远不会被描述为高阶函数。但是在 Haskell 中，因为函数是柯里化(Currying)的，所以上面的签名实际上只是括号版本的简写:

a -> (a -> a)

这显然是一个高阶函数。它需要一个 a并产生 a -> a 类型的函数. (回想一下，返回一个函数是 HOF 的特征之一。)正如我所说，在 Haskell 中，这两个签名是一回事。 (+)真的是一个高阶函数——我们只是经常没有注意到，因为我们打算给它两个参数，我们真正的意思是给它一个参数，产生一个函数，然后给这个函数第二个参数。多亏了 Haskell 方便、无括号的语法，用于将函数应用于参数，实际上并没有任何区别。 (这再次与非函数式语言形成对比:那里的加法“函数”总是正好有 2 个参数，只给它一个通常会出错。如果语言有一流的函数，你确实可以定义柯里化(Currying)形式，例如，在 Python 中:

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

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

所以，如果我们考虑到柯里化(Currying)，你教授的说法是完全正确的。

好吧，除了我上面提到的以下异常(exception)。我一直在假设带有表单签名的东西

a -> b

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

type MyFunctionType = Int -> Int

然后是一个带有签名的函数 MyFunctionType -> a或 a -> MyFunctionType肯定是 HOF，即使从签名上看它并不“看起来像一个”。

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