哈斯克尔:返回多路树的所有叶子

Question

>返回二叉树的所有叶子非常简单：

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的问题。

Answer 1

您可能

有兴趣看到这两种情况下的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)

Answer 2

我认为您的代码中存在错误，您将树的所有节点添加到叶子列表中，这是错误的，您需要检查某个节点是否是叶子，然后才能将其添加到列表中。

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)