Haskell：返回一個多路樹的所有葉子？

返回二叉樹的所有葉子很簡單：Haskell：返回一個多路樹的所有葉子？

data BinTree a = Empty | Node (BinTree a) a (BinTree a) deriving (Eq, Show) 

getLeaves :: BinTree a -> [a] 
getLeaves Empty = [] 
getLeaves (Node left current right) = [current]++getLeaves left++getLeaves right

那如果樹不是二進制而是多路樹的情況下（即在樹中的每個節點可以有任意數量的子節點和葉子）？

data MWTree a = Empty | Node [MWTree a] deriving (Eq, Show)

我不想找人爲我發佈解決方案;我只是不確定通用Haskell概念可能值得學習解決這種類型樹編寫getLeaves的問題。

來源

2014-09-21 Govind Parmar

您可能有興趣看到getLeaves在這兩種情況下都可以以Foldable或Traversable的模式實施。 Foldable具有toList :: Foldable f => f a -> [a]，其編碼收集所有值在Foldable容器f中的想法。 Traversable具有更強大的traverse :: (Applicative f, Traversable t) => (a -> t b) -> (f a -> t (f b))，其編碼在Traversable容器t上的某種遍歷的想法。 Traversable意味着Foldable

newtype K b a = K { unK :: b } deriving Functor 

instance Monoid b => Applicative (K b) where 
    pure = K mempty 
    K e <*> K f = K (e <> f) 

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> (t a -> m) 
foldMapDefault f = unK . traverse (K . f)

來源

2014-09-21 04:31:32

我認爲這是在你的代碼中的錯誤，要添加的樹的所有節點葉子的名單，這是不對的，你需要檢查一些節點是否爲葉或不要將它添加到列表中。

data BinTree a = Empty | Node (BinTree a) a (BinTree a) deriving (Eq, Show) 

getLeaves :: BinTree a -> [a] 
getLeaves Empty = [] 
getLeaves (Node Empty current Empty) = [current] 
getLeaves (Node left current right) = getLeaves left++getLeaves right

所以同樣的非二進制樹（我認爲這是一個錯誤在這裏太在你的代碼）

data MWTree a = Empty | Node a [MWTree a] deriving (Eq, Show) 

getLeaves :: (Eq a) => MWTree a -> [a] 
getLeaves Empty  = [] 
getLeaves (Node current []) = [current] 
getLeaves (Node current children) = if all (==Empty) children 
           then [current] 
           else (children >>= getLeaves) 
           --else concat $ map getLeaves children (another way of writing the same thing)

來源

2014-09-21 06:12:54

Haskell：返回一個多路樹的所有葉子？

回答

相關問題