在Haskell中hi ::(b - > c) - >(a - > b) - >(a - > c)

Question

我在Haskell中有以下类型签名:

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

我想写一个具体的实现,但我真的很难理解从哪里开始.我知道hi需要一个函数(b - > c),它返回一个函数(a - > b),它最终返回一个函数(a - > c).

谁能告诉我一个具体实现的例子？我怎么知道从哪里开始这样的事情以及定义左侧的内容？

Answer 1

想到这一点的一种方法是作为一个函数,它接受a (b -> c)和a (a -> b)并返回另一个函数(a -> c).那么让我们从那开始吧

hi f g = undefined       -- f :: b -> c, g :: a -> b

我们知道返回类型必须是一个函数(a -> c)-

hi f g = \a -> undefined -- f :: b -> c, g :: a -> b

我们现在有型的东西a在右手边,我们有一个功能,g :: a -> b所以明智的做法(实际上,我们所能做的唯一的事情)是适用g于a

hi f g = \a -> g a       -- ok, this fails to typecheck...

表达式g a有类型b,而且f :: b -> c,我们希望最终得到一个c.再说一遍,我们只能做一件事 -

hi f g = \a -> f (g a)

这种类型检查!我们现在开始清理过程.我们可以移动a到等号的左边

hi f g a = f (g a)

而且,如果您碰巧知道合成运算符,.您可能会注意到它可以在这里使用

hi f g a = (f . g) a

现在a双方都是多余的(这称为eta减少)

hi f g = f . g

我们可以.使用函数形式将运算符拉到表达式的前面(.)

hi f g = (.) f g

现在g和f它们都是多余的(eta减少的另外两个应用)

hi = (.)

所以你的功能hi只不过是功能组合.

Answer 2

您读错了：该->运算符是右结合的。因此，您的签名是：(b->c) -> ((a->b) -> (a->c))。因此，您可以将其理解为：给定一个函数 from bto c，它返回一个函数，该函数接受一个函数 from ato bto 最后返回一个函数 from ato c。

从那里，您应该能够自己解决这个练习。