包含函数的数据类型的函子实例

Question

我有一个数据类型定义为

data Foo a = Foo a (a -> a)

该Foo数据构造函数有两个参数值和功能。我需要为此编写 Monad 和 Monad 转换实例。

我正在尝试实现函子实例，

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) (g .(f x))

但我有一个错误Couldn't match type ‘a’ with ‘b’。

这是正确的，因为g只接受类型a并f x会转换a->b。所以接下来我重写为

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) g

我遇到了同样的错误“无法将类型 'a' 与 'b' 匹配”。

我也试过这个

instance Functor Foo where 
  fmap f (Foo x g) = Foo (f x) (f. g x)

我得到Occurs check: cannot construct the infinite type: a ~ b -> a 了(g.x)

我被卡住了，我知道函数g只接受 typea并返回 type a。但fmap会将 type 转换a为 type b。我想我已经申请fmap了g为好，这我无法做到。

如何编写上述数据类型的实例？

Answer 1

让我们考虑类型，我们基本上需要将 a 转换Foo a为 a Foo b，这意味着我们需要找到给定一个函数a -> b，一个 type 元素a和一个type函数，一个typea -> a元素b和一个 type 函数b -> b。

尤其是最后一个比较困难，因为我们只给定了一个 type 的函数a -> b，而不是一个 type 的函数b -> a，我们不能先将输入转换为 a a，然后通过原始函数进行处理，然后将其映射回 a b。

制作满足类型的映射并非完全不可能，例如：

fmap1 f (Foo x g) = Foo (f x) (const (f x))

或者：

fmap2 f (Foo x g) = Foo (f x) id

但是存在和需要满足法律的问题：fmap1fmap2

fmap id = id

换句话说，fmap id (Foo x g)需要等于Foo x g，现在如果我们使用idor const (f x)，那么id和f x并不总是等于g，至少不是 ifg是一个可以采用任何形式的函数。

如果您当然考虑Foo x g并且Foo x (id x)例如是等效的，这在某些情况下可能是合理的，正如@leftaroundabout 所说，那么您可以将其实现为函子实例。