haskell - 玫瑰树解构者

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 看起来像这样:

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