Wie filtert man einen Baum basierend auf einer bestimmten Bedingung in Haskell?

Question

Ich habe einen Baum Datentyp wie folgt definiert:

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

und ich will diesen Baum auf einer bestimmten Bedingung filtern. Die Funktion, die ich versuchte zu schreiben ist:

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) 

diese Funktion nicht richtig auf die Tatsache zurückzuführen arbeitet, dass die Funktion nichts im Fall zurückkehren muss, wo keiner der beiden Blattwerte (am Ende) die Bedingung erfüllt, . Ich wäre Ihnen dankbar, wenn Sie mir helfen könnten.

Answer 1

Ein Teil des Problems ist, dass Sie einfach keine Möglichkeit haben, einen leeren Baum darzustellen.

-- 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) 

Dies ist keine große Lösung; Es bleibt Ihnen immer noch mit mehreren Möglichkeiten, im Wesentlichen den gleichen Baum zu repräsentieren, da Empty und T Empty Empty nicht signifikant unterschiedlich sind. Sie könnten schreiben eine andere Funktion, die solche Bäume "Pflaumen".

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

, die in Ihre filterT Funktion eingebaut werden kann, etwa so:

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) 

Sie auch prune verlängern könnte der gleiche Baum einflügelige Bäume auf ein einzelnes Blatt (sollte Tree (Leaf 3) Empty und Leaf 3 betrachten zu kontrahieren ?), wie in

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) 

schließlich, ob Sie verwenden prune wird depe nd ob der gefilterte Baum die Struktur des Originals erhalten soll; Vielleicht möchten Sie beispielsweise zwischen einem Blatt und einem Knoten unterscheiden, der früher zwei Kinder hatte.

Answer 2

Es besteht die Möglichkeit, dass kein Artikel im gesamten Baum die Bedingung erfüllt. Dann haben Sie einen leeren Baum. Also muss man entweder die Definition des Baums erweitern:

data Tree a = Empty | Leaf a | Node (Tree a) (Tree a) 

, das ist, gehören der Fall für einen Empty Baum oder die Unterschrift des filterT ändern:

filterT :: (a -> Bool) -> Tree a -> Maybe (Tree a) 

dass so machen es möglich, zurückgeben Nothing.

mit dem zweiten Ansatz gehen ⁽¹⁾, wäre eine Möglichkeit, eine Foldable Instanz abzuleiten und die Filterfunktion in Bezug auf die richtige Falte definieren:

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving Show 

instance Foldable Tree where 
    foldr f z (Leaf x) = f x z 
    foldr f z (Node l r) = foldr f (foldr f z r) l 

filterT :: (a -> Bool) -> Tree a -> Maybe (Tree a) 
filterT f = foldr go Nothing 
    where 
    go x z = if not (f x) then z else Just $ case z of 
    Nothing -> Leaf x 
    Just tr -> Node (Leaf x) tr 

---

_{1. weil Es hält den Datentyp einfacher und vermeidet redundante Node Empty Empty Werte.}