FP:在“高阶”函数中，“顺序”是什么意思？递归函数是“高阶”函数吗？

Question

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

f.g.h

那么它被称为"3阶“函数吗？

“高阶”函数是静态函数积累的概念吗？然后，当我有一个递归函数f时，在运行时，它的调用堆栈类似于f。我们可以说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))

甚至被认为是三阶函数。

Answer 2

一个例子(javaish)

Function<Double, Double> oneOf(Function<Double, Double>... fs) {
     return fs[new Random().nextInt(fs.length)];
}

double y = oneOf(cos, sin, atan).applyTo(1.23);

这是2级，原因有两个:参数类型，特别是结果类型是函数。