Defining fmap for a RoseTree

Question

我正在尝试为RoseTree数据类型编写Functor实例。

data Rose a = MkRose a [Rose a]
deriving (Eq, Show)

instance Functor Rose where
fmap f (MkRose a children) = MkRose (f a) (fmap f children)

我真的认为这将工作，但我得到:

Expected type: [a]
Actual type: [Rose a]

对于孩子，谁能给我解释一下我错在哪里?

Answer 1

data Rose a = MkRose a [Rose a]
deriving (Eq, Show)

instance Functor Rose where
fmap f (MkRose a []) = MkRose (f a) []
fmap f (MkRose a roses) = MkRose (f a) ((fmap . fmap) f roses)

您面临的问题是由于Rose的子节点被打包在一个额外的数据结构中，即列表[]。你有一个递归的数据结构，每一步都有无限多个分支，比如递归路径。换句话说，它不像列表那样只有一条路径，也不像二叉树那样只有2或3条路径，这些路径的分支通常用特定的数据构造器命名，但每个节点可以有无限多个子节点。

因此，您需要通过使用fmap . fmap构造向下钻取以访问您正在寻找的值。右边的fmap(ghc为其提供了内置的Functor)遍历列表中的每个元素，并将它们传递给左边的fmap，后者钻取MkRose的值，您已经为其编写了Functor。

如果你看fmap的签名，你有:

fmap :: Functor f => (a -> b) -> f a -> f b

将此应用于[]得到:

fmap @[] :: (a -> b) -> [a] -> [b]

在我们的案例中，这是fmap . fmap中右fmap的签名。

类似地，将fmap应用于Rose，得到签名:

fmap @Rose :: (a -> b) -> Rose a -> Rose b

这两个家伙的组合将右边的输出作为左边的输入，左边的与f一起作用于它的输入，即玫瑰。

Answer 2

当f :: a -> b,fmap f对于任意一个函子F具有类型F a -> F a时。例如，我们可以使用

fmap f :: [a] -> [b]
fmap f :: Rose a -> Rose b   -- in recursive calls
fmap f :: Maybe a -> Maybe b
fmap f :: IO a -> IO b
...

我想你明白我的意思了。然而，如果我们有两个函子，那么仅fmap f是不够的。例如，我们没有

fmap f :: Maybe [a] -> Maybe [b]

是因为fmap只适用于单个函子，而这里我们有两个函子(Maybe和[])。如果需要使用嵌套的函函数，则需要fmap:

f             :: a -> b
fmap f        :: [a] -> [b]               -- add []
fmap (fmap f) :: Maybe [a] -> Maybe [b]   -- add Maybe

在你的例子中，你需要[Rose a] -> [Rose b]类型的东西，它涉及两个函子，所以你也必须两次使用fmap。