CODEWITHSUNDEEP
haskell
altern
altern

Reputation: 5949

Filtering out elements in RoseTree

I am trying to write a function filterTree that would filter out elements in RoseTree using given condition:

data RoseTree a = RoseTree a [RoseTree a]
                   deriving (Show, Functor)

extractChild :: RoseTree a -> RoseTree a
extractChild (RoseTree _ (x:[])) = x
extractChild rTree = rTree

filterTree :: ( a -> Bool ) -> RoseTree a -> RoseTree a
filterTree condition rTree@(RoseTree a list) = 
    if (condition $ a) 
      then (extractChild rTree)  
      else (RoseTree a (filterTreeList condition list)) 

filterTreeList :: (a -> Bool) -> [RoseTree a] -> [RoseTree a]
filterTreeList condition [] = []
filterTreeList condition (x:xs) = [filterTree condition x] ++ (filterTreeList condition xs)

But it does not work quite as expected. For some reason it does not filter out nested elements that satisfy the condition. For example, if I run 

filterTree (==2) (RoseTree 1 [ RoseTree 2 [ RoseTree 3 [] ]])

then it runs fine returning RoseTree 1 [RoseTree 3 []]. But if I run it with one more nested element that satisfies the condition

filterTree (==2) (RoseTree 1 [ RoseTree 2 [ RoseTree 3 [RoseTree 2 [RoseTree 1[]]] ]])

then it returns erroneous result having second matching element in the list: RoseTree 1 [RoseTree 3 [RoseTree 2 [RoseTree 1 []]]]

Any ideas why this might be happening?

Upvotes: 0

Views: 226

Answers (1)

James Wilcox
James Wilcox

Reputation: 5663

The following works for me on the examples you provided.

Note that it will loop if a node ever matches the filter condition and does not have exactly one child.

filterTree :: ( a -> Bool ) -> RoseTree a -> RoseTree a
filterTree condition rTree@(RoseTree a list) = 
    if (condition $ a) 
      then filterTree condition (extractChild rTree)
      else (RoseTree a (filterTreeList condition list))

Upvotes: 2

Related Questions