解释高阶函数的类型签名？

Question

function :: (t2 -> t1) -> (t1 -> t) -> t2 -> t
function f1 f2 x = f2 (f1 x )

function1 :: (t -> t) -> t -> t
function1 f1 x = f1 (f1 x)

function11 :: (t1 -> t1) -> t -> t1 -> t1
function11 f1 f2 x = f1 (f1 x)

function3 :: (t1 -> t1) -> t -> t1 -> t1
function3 f1 f2 x = f1 (f1 (f1 x))

function4 :: (t1 -> t1) -> t -> t1 -> t1
function4 f1 f2 x = f1 (f1 (f1 x))

谁能解释前两个的类型签名以及为什么后三个的类型签名相同？我正在阅读有关高阶函数的内容，但我还没有想到它们是什么。

Answer 1

Can anyone explain the type signatures for the the first two?

让我们为类型变量取一些更易读的名称。

function :: (in -> tmp) -> (tmp -> out) -> in -> out
function f1 f2 x = f2 (f1 x )

这种类型表示：如果你给我一个将输入转换为临时值的函数，以及一个将临时值转换为输出的函数，我将还给你一个将输入转换为输出的函数。您可以想象画一个 "data processing pipeline"，其中我们有一堆各种类型的对象，以及将一种类型的值转换为另一种类型的值的操作。例如，这就是我如何在视觉上绘制您的 function:

in    ----- f1 ----->    tmp    ----- f2 ----->    out
  \                                               ^
   \                                             /
    `------------- function f1 f2 --------------'

此处的预期解释是，您可以想象在此管道中采取两条路线——您首先使用操作 f1，然后使用操作 f2；或者你可以使用操作 function f1 f2 一次完成整个事情。

function1 :: (t -> t) -> t -> t
function1 f1 x = f1 (f1 x)

在这里，function1 接受一个函数来转换 ts（到其他 ts），并返回一个（可能不同的）函数来转换 t s（再次，进入其他 ts）。同样，为此绘制数据处理管道，您可能会得到这样的结果：

t    ----- f1 ----->    t    ----- f1 ----->    t
 \                                             ^
  \                                           /
   `------------- function1 f1 --------------'

Why is the type signature for the last 3 the same?

让我们快速回顾一下最后三个函数的定义：

function2 f1 f2 x = f1 (f1 x)
function3 f1 f2 x = f1 (f1 (f1 x))
function4 f1 f2 x = f1 (f1 (f1 x))

好的，关于 function2、function3 和 function4 的第一个有趣的事情是它们采用三个参数，f1、f2，和 x，但它们中的每一个都完全忽略了 f2——它们中的任何一个都没有在 = 的右侧提及。其次，function3 和 function4 的定义方式完全相同，因此可以赋予它们相同的类型也就不足为奇了。

考虑到这两件事，我们可以稍微缩小问题的范围，这样我们就可以问为什么这两个函数具有类型签名：

function2' f x = f (f x)
function3' f x = f (f (f x))

具体来说，他们的共享类型签名是这样的：

(t -> t) -> (t -> t)

正如我们上面讨论的 function1，这意味着它们对 t 进行了转换，并且它们也恰好对 t 进行了转换。再次考虑数据处理管道，现在应该很清楚为什么它们具有相同的类型：我们在管道中两次或三次应用我们的函数 f 并不重要；类型没有改变：

   .------------------------ function3' f ------------------------.
  /                                                                \
 /                                                                  v
t    ----- f ----->    t    ----- f ----->    t    ----- f ----->    t
 \                                           ^
  \                                         /
   `------------ function2' f -------------'

假设 f 是一个从标记为 t 的节点开始并在标记为 t 的节点结束的函数，那么无论我们应用多少次 f在停止之前，我们总是回到一个从标记为 t 的节点开始并在标记为 t.

的节点结束的函数

Answer 2

当一个函数将其他函数作为输入参数或returns其他函数作为值时，它被称为高阶函数。

在你的第一种情况下，名为 function 的函数有两个函数 (t2 -> t1) 和 (t1 -> t) 类型以及 t2 类型的值。你可以使用 ghci 来更好地了解它的作用：

λ> :t id
id :: a -> a
λ> id 3
3
λ> function id id 3
3
λ> function id (\x -> x + 3) 3
6
λ> function (\x -> x + 3) (\x -> x + 3) 3
9

在您的 function1 中，您将单一函数和类型 t 的值作为输入。

why the type signature for the last 3 are the same?

因为他们接受相同的输入。编译器足够聪明，可以推断出您传递的第二个参数是 t -> t1 类型的函数，即使您没有给出任何括号。我会建议你给括号，因为它提高了可读性很多。

正如 Daniel Wagner 指出的那样，您没有在最后三个定义中使用 f2 输入。所以，你甚至可以给它传递一个底值，它不需要是一个函数：

λ> function4 id undefined "hello"
"hello"

解释高阶函数的类型签名？

Explain the type signatures for High order functions?

haskell

type-signature