CODEWITHSUNDEEP
haskelltree
user17588651
user17588651

Reputation:

Deleting an element from a rose tree in Haskell

I am trying to delete an element from a rose tree in Haskell by giving the name of the parent of the node and the name of the node:

I have written this but it does not compile

deleteNode x parent (Branch x' trees) 
    | parent == x' = Branch x' $ if (head trees) /= x then ((Branch x []):trees) else []
    | otherwise = Branch x' $ (deleteNode x parent) <$> trees

The error is:

tree.hs:25:75: error:
    * Occurs check: cannot construct the infinite type: t ~ Rose t
      Expected type: [Rose (Rose t)]
        Actual type: [Rose t]
    * In the second argument of `(:)', namely `trees'
      In the expression: ((Branch x []) : trees)
      In the second argument of `($)', namely
        `if (head trees) /= x then ((Branch x []) : trees) else []'
    * Relevant bindings include
        trees :: [Rose t] (bound at tree.hs:24:32)
        x' :: t (bound at tree.hs:24:29)
        parent :: t (bound at tree.hs:24:14)
        x :: Rose t (bound at tree.hs:24:12)
        deleteNode :: Rose t -> t -> Rose t -> Rose t
          (bound at tree.hs:24:1)
Failed, modules loaded: none.

I have the following definition of a Rose tree

data Rose a = Empty | Branch a [Rose a] deriving (Show, Eq)

How to make it work and return a new tree that does not contain the specified element?

Upvotes: 1

Views: 135

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476547

It is not clear to me why you need the parent here. You can implement a view as:

deleteNode :: Eq a => a -> Rose a -> Rose a
deleteNode _ Empty = Empty
deleteNode x (Branch x' trees) 
    | x == x' = Empty
    | otherwise = Branch x' $ (deleteNode x) <$> trees

In case we thus found the item (x == x'), then we return Empty, otherwise we recurse on the leaves.

Note that this function will remove all branches that have x as "label", so if there are multiple directories foo/, it will remove all of them.

If parent is the name of the parent node, you can work with:

deleteNode :: Eq a => a -> a -> Rose a -> Rose a
deleteNode _ _ Empty = Empty
deleteNode parent x (Branch x' trees) 
  | parent == x' = Branch x' (map (go x) trees)
  | otherwise = Branch x' $ (deleteNode parent x) <$> trees
  where go _ Empty = Empty
        go x b@(Branch x' _)
          | x == x' = Empty
          | otherwise = b

This will remove all items which have as label of the parent Branch the value parent, and x as own value. There can however still be multiple items in the tree with foo as parent, and bar as label such that these will all be removed.

Upvotes: 0

Related Questions