玫瑰樹解構

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 

Answer 2

subtrees :: Rose a -> [Rose a] 
subtrees (_ :> rs) = rs 

label :: Rose a -> a 
label (a :> _) = a