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：返回一个多路树的所有叶子？

回答

相关问题