玫瑰树解构主义者

Question

如果我们有玫瑰树定义如下:

data Rose a = a :> [Rose a]

然后我知道:>是一个中缀构造函数.但是你如何使用这种树的元素呢？如何遍历它以访问节点或提取子树或元素？

Answer 1

您可以像这样在构造函数上进行模式匹配(例如):

find :: (Eq a) => a -> Rose a -> Bool
find item (top :> rest)
  | item == top = True
  | otherwise = any (find item) rest

解决您的第二个问题:是的,您可以在不了解仿函数的情况下执行此操作,但创建仿函数实例是有意义的,因为它可以使您的数据结构更加灵活.但是让我们开始业务:map处理每个节点的A 看起来像这样:

myMap :: (a -> b) -> Rose a -> Rose b
myMap f (node :> rest) = f node :> map (myMap f) rest

这很容易添加到仿函数类型类中,因为它完全符合我们的要求:

instance Functor Rose where
  fmap :: (a -> b) -> Rose a -> Rose b
  fmap = myMap