如何实现这个更高阶的功能

Question

我是函数式编程的新手,我正在尝试解决以下练习;

---

鉴于类型

type Cont r a = (a -> r) -> r

实现以下高阶函数

mapReader :: (a -> b) -> (Cont r a) -> Cont r b

---

第一步是简化类型,它给出:

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r

接下来,定义需要在此函数中提供的参数.这些参数是我们得到的三个函数

mapReader :: (a -> b) -> ((a -> r) -> r) -> (b -> r) -> r
mapReader f g h = _1

从这里,我们可以定义以下类型:

f :: a -> b
g :: (a -> r) -> r
h :: b -> r
_1 :: r

但是现在我被卡住了.导致r的函数有两个,其中一个函数包含另一个函数(a - > r).我怎样才能开始定义r？任何提示都非常感谢!

Answer 1

我们有

f :: a -> b
g :: (a -> r) -> r
h :: b -> r

我们需要

_1 :: r

我们可以通过两种方式制作r:g和h.

我们来试试吧h.h采用类型的参数b.获得其中之一的唯一方法是使用f.f采用类型的参数a,并且...我们没有办法获得其中一个.

所以现在让我们尝试使用g:

mapReader f g h = g _2

被告诉

_2 :: a -> r

由于我们正在构建一个函数,我们可以像往常一样应用lambda抽象:

mapReader f g h = g (\a -> _3)

a :: a
_3 :: r

别急......现在我们有一个a,所以我们可以回到我们的第一次尝试:

mapReader f g h = g (\a -> h (f a))

或者,更紧凑,

mapReader f g h = g (h . f)

如果不是要回的第一次尝试,我们做到了第二种方式再次？

mapReader' f g h =
  g (\a1 -> g (\a2 -> _4))

_4 :: r

你可以永远这样,但你也可以通过两种不同的方式来到这里:

mapReader2 f g h =
  g (\_ -> g (h . f))

mapReader3 f g h =
  g (\a1 -> g (\_ -> h (f a1)))

Oy公司!这三种不同的函数都具有相同的类型,如图所示,这种方法可用于生成无限的函数族!你怎么决定你想要哪一个？你必须考虑这个意图.g的论证是延续,所以你想用你传递的东西组成一个函数g,而不是g多次调用.所以mapReader是"正确"的答案.

更准确地说,mapReader应该将态射映射为连续函子.这尤其需要

mapReader id = id

那是,

mapReader id g h = g (h . id)
  = g h

对于正确的定义,这是无条件的,但对于任何其他定义都没有.