haskell - 如何在Haskell中根据特定条件过滤树？

Question

我定义了树数据类型如下:

data Tree a = T (Tree a, Tree a) | Leaf a deriving (Show, Eq, Ord)

我想根据特定条件过滤这棵树。我尝试编写的函数是:

filterT :: (a -> Bool) -> Tree a -> Tree a
filterT c (T(Leaf x,T(t1,t2))) = if c x 
                                then (T(Leaf x, T(filterT c t1, filterT c t2)))
                                else T(filterT c t1,filterT c t2)

该函数无法正常工作，因为在两个叶子值(最后)都不满足条件的情况下，该函数没有任何可返回的内容。如果您能提供帮助，我将不胜感激。

Answer 1

部分问题在于您根本没有办法表示空树。

-- Get rid of unnecessary tuple
data Tree a = Empty 
            | Leaf a 
            | T (Tree a) (Tree a) deriving (Show, Eq, Ord)

-- A filtered empty tree is still empty
filterT p Empty = Empty
-- A leaf either stays the same or becomes empty
filterT p (Leaf x) | p x = Leaf x
                   | otherwise = Empty
-- Any other tree is just the result of filtering each child
filterT p (T left right) = T (filterT p left) (filterT p right)

这不是一个很好的解决办法；它仍然让您有多种方式来表示本质上相同的树，因为 Empty 和 T Empty Empty 没有显着不同。您可以编写另一个函数来“修剪”此类树。

prune :: Tree a -> Tree a
prune (T Empty Empty) = Empty
prune x = x

可以将其合并到您的 filterT 函数中，如下所示:

filterT _ Empty = Empty
filterT p (Leaf x) | p x = Leaf x
                   | otherwise = Empty
filterT p (T left right) = let prune (T Empty Empty) = Empty
                               prune x = x
                          in prune $ T (filterT p left) (filterT p right)

您还可以扩展 prune 将单叶树收缩为单叶(应该 Tree (Leaf 3) Empty 和 Leaf 3被认为是同一棵树吗？)，如

filterT' _ Empty = Empty
filterT' p (Leaf x) | p x = Leaf x
                    | otherwise = Empty
filterT' p (T left right) = let prune (T Empty Empty) = Empty
                                prune (T (Leaf x) Empty)) = Leaf x
                                prune (T Empty (Leaf x)) = Leaf x
                                prune x = x
                            in prune $ T (filterT p left) (filterT p right)

最后，是否使用prune将取决于过滤后的树是否应保留原始结构；例如，也许您想区分叶子和曾经有两个子节点的节点。