recursion - FP : What does "order" mean in "high order" functions? 递归函数是否为 "high order"函数？

Question

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

f.g.h

那么它叫“三阶”函数吗？

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

非常感谢。

Answer 1

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

This lecture slide on Functional Programming定义

The order of data

• Order 0: Non function data
• Order 1: Functions with domain and range of order 0
• Order 2: Functions with domain and range of order 1
• Order k: Functions with domain and range of order k-1

所以基本上零阶函数不是函数，一个只对数据进行操作的一阶普通函数，其他一切都是高阶函数。

(These slides 似乎有差一错误)

让我们来看一些 (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 = (+)

柯里化(Currying)函数的类型实际上是 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 它确实有一个一阶函数作为输入和一个零阶结果，使其成为二阶总体而言。

以及我们所知道的柯里化(Currying)组合运算符

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

甚至会被认为是三阶函数。