haskell - 包含函数的数据类型的仿函数实例

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只接受 a 类型的并返回类型 a .但是 fmap将转换类型 a输入 b .我想我必须申请 fmap超过 g同样，我做不到。
如何为上述数据类型编写实例？

Answer 1

让我们考虑类型，我们基本上需要转换 Foo a到 Foo b ，这意味着我们需要找到，给定一个函数 a -> b , a 类型的元素和一个类型为 a -> a 的函数, b 类型的元素和 b -> b 类型的函数.
尤其是最后一个很困难，因为我们只得到了一个类型为 a -> b 的函数。 , 而不是 b -> a 类型的函数，我们不能先将输入转换为a ，然后通过原始函数对其进行处理，然后将其映射回b .
制作满足类型的映射并非完全不可能，例如:

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

或者:

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

但是 fmap1 的问题和 fmap2需要满足法律:

fmap id = id

换句话说 fmap id (Foo x g)需要等于 Foo x g , 现在如果我们使用 id或 const (f x) ，然后 id和 f x并不总是等于 g , 至少如果 g是一个可以采取任何形式的函数。
如果你当然考虑 Foo x g和 Foo x (id x)例如等价，在某些情况下可能是合理的 @leftaroundabout says ，那么您可以将其实现为仿函数实例。