Haskell

Question

我在为自定义数据类型（我无法更改）编写自己的仿函数实例时遇到问题。数据类型定义为：

data Foo a = Baz String (Qux -> Foo a) | Bar a
data Qux = None | Quux String

我的问题是为 Foo 类型编写仿函数。具体来说，我不确定如何将仿函数函数 f 正确应用到 Foo 中的函数。我正在考虑以某种方式在构造函数中调用该函数，但由于我没有任何可用的 Qux，所以我被卡住了。

instance Functor Foo where
    fmap f (Bar a) = Bar (f a)
    fmap f (Baz s ???) = Baz s (???) -- What goes here?

    -- Clearly, something like this doesn't work
    -- fmap f (Baz s g) = Baz s (f g) 

    -- I've also tried something like this, but I'm not sure where to go from there
    -- fmap f (Baz s (None   -> Bar b)) = Baz s (f b) ???
    -- fmap f (Baz s (Quux x -> Bar b)) = Baz s ???

Answer 1

让我们从完成这个等式的左边开始。我们可以写 g 来将你的函数绑定到一个变量。

fmap f (Baz s g) = Baz s (???)

然后，我们需要用另一个函数来填充问号，它需要一个 Qux 和 returns 一个 Foo b.

fmap f (Baz s g) = Baz s (\q -> ???)

我们只能对 q 做一件事，即对其应用 g。

fmap f (Baz s g) = Baz s (\q -> g q)

然而，这给了我们一个Foo a，但我们需要一个Foo b！我们没有这样做的功能。然而，我们确实有 f，它需要一个 a 和 returns 一个 b。要是有办法把 a -> b 变成 Foo a -> Foo b 就好了……哦等等，有，它叫 fmap！

fmap f (Baz s g) = Baz s (\q -> fmap f (g q))

如果您想用无点表示法 (https://wiki.haskell.org/Pointfree) 编写函数，您可以改为这样做。

fmap f (Baz s g) = Baz s (fmap f . g)

Answer 2

遵循类型：

fmap f (Baz s g) = GOAL
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- GOAL :: Foo b

所以我们正在寻找 Foo b（目标线）。我们可以用 Bar 或 Baz 制作一个。 fmap 应该保留结构，所以它应该是 Baz。 Baz 的 String 参数可能不应该改变，只是第二个参数引起了问题。

fmap f (Baz s g) = Baz s GOAL
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- GOAL :: Qux -> Foo b

现在我们要做一个Qux -> Foo b。如果你需要做一个函数，lambda 是必不可少的工具（还有其他工具，但 lambda 是祖父）。所以做一个 lambda:

fmap f (Baz s g) = Baz s (\x -> GOAL)
   -- f    :: a -> b
   -- s    :: String
   -- g    :: Qux -> Foo a
   -- x    :: Qux          <-- NEW
   -- GOAL :: Foo b

请注意，我们现在有一个 x :: Qux 可以使用。使用g和x我们可以得到一个Foo a，然后使用fmap f递归¹ 我们可以制作所需的 Foo b.

请注意我是如何一次一小步地填写表达式，用目标替换未知参数，然后退后一步考虑我在范围内有哪些变量以及它们的类型是什么。继续这样做，直到目标明确。

¹ 递归类型通常会有相应的递归fmap定义。 fmap 中递归发生的位置与类型递归的方式完全对应。

Haskell - 具有函数构造函数的数据类型的自定义仿函数实例

Haskell - Custom functor instance on data type with function constructor

functor