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并返回一个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并返回一个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（GOAL系列）。我们可以用Bar或Baz制作一个。 fmap应该保留结构，所以它应该是Baz。 String对Baz的论证可能不应该改变，它只是造成问题的第二个论点。

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是granddaddy）。所以做一个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 f1我们可以制作所需的Foo b。

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

---

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