对于带有嵌套的可能值的Tree数据类型，可遍历实例应该是什么样的呢？
我在三天内有一个Haskell考试，所以我想我应该练习一下，然后复习一下过去的考试，其中一个考试的特点是树形数据类型：
data Tree a = Leaf1 a | Leaf2 a a | Node (Tree a) (Maybe (Tree a)) deriving (Eq, Ord, Show)起初看起来并不是那么有挑战性，但后来我意识到我必须为这棵树编写一个可遍历的实例。处理树叶很容易：
instance Traversable Tree where
traverse f (Leaf1 a) = Leaf1 <$> f a
traverse f (Leaf2 a b) = Leaf2 <$> f a <*> f b然而，我开始在节点上遇到问题。
traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
traverse f (Node l (Just r)) = Node <$> traverse f l <*> Just (traverse f r)当然，这些都不起作用，而且我也无法思考在第二个<*>之后应该发生什么。我试着使用漏洞，但是ghci给我的消息没有多大帮助(我知道问题在于类型，但我不知道该如何修复它)。
下面是我试图编译它时收到的错误消息：
* Couldn't match type `f' with `Maybe'
`f' is a rigid type variable bound by
the type signature for:
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Tree a -> f (Tree b)
at exam.hs:92:3-10
Expected type: f (Maybe (Tree b))
Actual type: Maybe (Maybe (Tree b))
* In the second argument of `(<*>)', namely `Nothing'
In the expression: Node <$> traverse f t <*> Nothing
In an equation for `traverse':
traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
* Relevant bindings include
f :: a -> f b (bound at exam.hs:94:12)
traverse :: (a -> f b) -> Tree a -> f (Tree b)
(bound at exam.hs:92:3)
|
94 | traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
| ^^^^^^^有人能给我一些指点或者解决这个问题的方法吗？
回答 2
Stack Overflow用户
发布于 2020-06-01 17:24:12
traverse允许您对数据结构的每个“插槽”应用“有效果的函数”，从而维护结构的形状。它的类型如下：
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)它依赖于这样一个事实，即“效果”的类型是一个Applicative。Applicatve提供哪些操作？
<$>.
- it使我们能够提升纯函数，并将它们应用到中有效的操作中，让我们将有效的操作与
(<*>) :: f (a -> b) -> f a -> f b结合起来。请注意，第二个参数是有效的操作，而不是纯值。pure :: a -> f a.允许我们获取任何纯值并将其置于有效的上下文中。
现在，当节点有一个Nothing时，由于没有任何值，所以没有要执行的效果，但是<*>仍然需要在右边执行有效的操作。我们可以使用pure Nothing使类型适合。
当节点有一个Just t时，我们可以使用函数a -> f b对类型为Tree a的子树t进行traverse，最后得到一个动作f (Tree b)。但是<*>实际上是在期待一个f (Maybe (Tree b))。取消的Node构造函数使我们期待。我们能做什么？
解决方案是使用Just将<$>构造函数提升到操作中，这是fmap的另一个名称。
注意，我们没有改变值的总体“形状”：Nothing仍然是Nothing，Just仍然是Just。子树的结构也没有改变:我们递归地对子树进行traverse，但不对它们进行修改。
Stack Overflow用户
发布于 2020-06-01 17:29:53
简单地说，您需要使用traverse来进入Maybe。
类型的Traversable和Foldable实例通常具有与其Functor实例类似的结构。而fmap将纯函数映射到结构上，将结果与纯构造函数组合起来：
instance Functor Tree where
fmap f (Leaf1 a) = Leaf1 (f a)
fmap f (Leaf2 a1 a2) = Leaf2 (f a1) (f a2)
fmap f (Node ta mta) = Node (fmap f ta) (fmap (fmap f) mta)注意(fmap (fmap f) mta)：外部fmap映射在Maybe上，内部映射在Tree上
(fmap
:: (Tree a -> Tree b)
-> Maybe (Tree a) -> Maybe (Tree b))
((fmap
:: (a -> b)
-> Tree a -> Tree b)
f)
mta相反，traverse将有效的函数映射到结构上，并相应地使用<$>和<*>操作符将构造函数提升到Applicative中：
instance Traversable Tree where
traverse f (Leaf1 a) = Leaf1 <$> f a
traverse f (Leaf2 a1 a2) = Leaf2 <$> f a1 <*> f a2
traverse f (Node ta mta) = Node <$> traverse f ta <*> traverse (traverse f) mta再次注意，我们必须traverse Maybe，在其中，traverse Tree，但是与纯函数a -> b不同，我们只有一个有效的函数a -> f b，给定Applicative f
(traverse
:: (Tree a -> f (Tree b))
-> Maybe (Tree a) -> f (Maybe (Tree b)))
((traverse
:: (a -> f b)
-> Tree a -> f (Tree b))
f)
mta同样，foldMap具有类似的结构，但它没有重构数据类型，而是使用Monoid实例组合结果：
instance Foldable Tree where
foldMap f (Leaf1 a) = f a
foldMap f (Leaf2 a1 a2) = f a1 <> f a2
foldMap f (Node ta mta) = foldMap f ta <> foldMap (foldMap f) mta下面是一个使用traverse的简单示例
> traverse (\ x -> print x *> pure (x + 1)) (Node (Leaf1 10) (Just (Leaf2 20 30)))
10
20
30
Node (Leaf1 11) (Just (Leaf2 21 31))使用DeriveFoldable、DeriveFunctor和DeriveTraversable扩展，您可以向数据类型添加deriving (Foldable, Functor, Traversable)子句，并使用-ddump-deriv标志查看生成的代码。
https://stackoverflow.com/questions/62136774
复制相似问题
腾讯云开发者
