FP：“高阶”函数中的“阶”是什么意思？递归函数是“高阶”函数吗？

Question

我怀疑当我们说“高阶”函数时，“阶”的真正含义是什么？例如，我有一个嵌入式函数调用，例如：

f.g.h

那么它被称为“三阶”函数吗？

“高阶”函数是静态函数累加的概念吗？那么当我有一个递归函数 f ，并且在运行时它的调用堆栈就像 ffff 时，我们可以说 f 是高阶函数吗？

多谢。

Answer 1

顺序基本上是类型中箭头的嵌套级别。

这张关于函数式编程的讲座幻灯片定义了

数据的顺序

• 订单 0：非功能数据
• 1 阶：定义域和值域为 0 阶的函数
• 2 阶：具有 1 阶定义域和值域的函数
• k 阶：具有 k-1 阶定义域和值域的函数

因此，基本上零阶函数不是函数，而是仅对数据进行操作的一阶普通函数，其他一切都是高阶函数。

（这些幻灯片似乎有一个相差一的错误）

让我们来看一些（Haskell）示例：

-- no arrow, clearly some plain data
x :: Int
x = 0

-- one arrow, so it's a first-order function:
add2 :: Int -> Int
add2 = (+ 2)

-- still one arrow only:
add :: (Int, Int) -> Int
add = uncurry (+)

-- and this is a first-order function as well:
add4 :: Int -> Int
add4 = add2 . add2

正如您所看到的，是否使用函数组合（高阶函数）来定义函数并不重要，只有它们的结果类型很重要。因此，您的f.g.h和f.f.f.f示例只是一阶函数（假设f是一个）。

高阶函数的简单示例是多元函数：

-- two arrows! Looks like a second-order function
plus :: Int -> Int -> Int
plus = (+)

柯里化函数的类型实际上是Int -> (Int -> Int)我们可以清楚地看到它是一个具有一阶函数作为结果的函数，因此它的阶数是 2。输入的低阶 (0) 并不重要。

我们可以在一个更有趣的例子中看到同样的情况，函数组合：

compose :: ((b -> c), (a -> b)) -> a -> c
compose (f, g) x = f (g x)

这里参数和结果都是一阶函数，因此compose都是 2 阶函数。

另一个例子是定点组合器fix :: (a -> a) -> a，它确实具有一阶函数作为输入和零阶结果，使其总体上是二阶。

以及我们所知的柯里化组合运算符

(.) :: (b -> c) -> ((a -> b) -> (a -> c))

甚至可以被视为三阶函数。