haskell 函数类型简化 f :: ((b -> a ) -> a -> c ) -> (b -> a ) -> b -> c

Question

只是寻找这个函数类型的解释，请

f x y z = x y (y z)

前奏说的是

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

但我无法用任何已知的方法得到那个结果 ¬¬

此致。

Answer 1

呃，那些“手动检查这个表达式”的练习太愚蠢了。我不知道为什么讲师总是把他们放在作业中。

在实践中，实际上更相关的是反过来：给定一个类型，找到一个实现。那么让我从这个角度回答这个问题：你已经知道了

f :: ((b -> a) -> a -> c) -> (b -> a) -> b -> c
--   ????????????????????    ????????   ???

...所以你有三个参数可以接受，足够合理地调用它们x，y并且z

f x y z = _

你最终在寻找一个c，而c你唯一可用的是在最终结果中x

    x :: (b -> a) -> a -> c
    --   ????????   ???

...这需要两个参数

f x y z = x _ _

...的类型b -> a和a。让我们检查一下我们有什么可用的

    y :: b -> a
    z :: b

太好了，我们可以直接y用作第一个参数

f x y z = x y _

对于第二个参数，我们需要一个a. 嗯，z是 a b，这不起作用，但是当给定 a 时会y产生a一个b，所以我们可以通过y z，因此最终得到

f x y z = x y (y z)

或者我们更喜欢用 Haskell 编写它，f x y = x y . y.

现在反过来：让我们从 ?-reduced 形式开始

f x y = x y . y

这是一个管道，所以让我们开始给传递参数一个名字 p

        x y . y :: p -> _

该参数首先传递给y，所以我们有

        y :: p -> _

它由此而来，因为y也是第一个参数x

        x :: (p -> _) -> _

此外，x然后接受（在管道中）任何来自y

        y :: p -> r
        x :: (p -> r) -> r -> _

让我们调用最终结果 q

        y :: p -> r
        x :: (p -> r) -> r -> q

并按照给定的方式写出整个函数：

(\x y -> x y . y) :: ((p -> r) -> r -> q) -> (p -> r) -> p -> q
--                   ??????????x?????????    ???y????

也就是说，在重命名类型变量后，与您开始时的相同。

Answer 2

从f x y z = x y (y z)，您可以推理如下：

• 我们不应用于z任何东西，所以它可以有一些任意类型；调用它u1（对于未知的第一）。

• y应用于z，因此其参数类型是u1，但返回类型是另一种未知类型u2。因此y :: u1 -> u2。

• y z因此有类型u2。

• x应用于y and y z，所以必须有一个像(u1 -> u2) -> u2 -> u3; 没有理由假设任一参数具有相同的类型，或者任一类型与返回类型相同。

• 的返回值f与 的返回值相同x，即u3。

综上所述，我们有

f :: ((u1 -> u2) -> u2 -> u3) -> (u1 -> u2) -> u1          ->    u3
     ------------------------    ----------    --                --
         type of x                type of y    type of z        end result of f

因为除了保持不同类型分开之外，各个类型变量的名称并不重要，我们可以使用

• u1 ~ b
• u2 ~ a
• u3 ~ c

获取您查找的类型

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