CODEWITHSUNDEEP
haskelltree
Marco
Marco

Reputation: 1460

Delete a node from a tree and return the resulting forest

I'm coming from a Java background and want to learn some Haskell. Bit stuck at the moment, though.

What I want to do is: I have a list of trees where each node has a unique identifier across all trees in the list. Now I want to delete one node out of one of these trees and return the new trees as well as the unchanged trees.

Deleting a node should:

Imagine the following trees:

enter image description here

When I delete node '2' I want the result to be the following trees:

enter image description here

Each node in a tree consists of the identifier and a list of child trees. Here is what I have so far, however it's obviously not working and I'm a bit lost on how I can solve this with Haskell:

import Data.Tree
data CustomNode = CustomNode { identifier :: Int } deriving (Ord,Eq,Show,Read)
type CustomTree = Tree CustomNode

myTree0 = t0
    where
        leaf i = Node CustomNode{identifier = i} []
        t0 = Node CustomNode{identifier = 0} [t1]
        t1 = Node CustomNode{identifier = 1} [t2, t5]
        t2 = Node CustomNode{identifier = 2} [leaf 3, leaf 4] 
        t5 = Node CustomNode{identifier = 5} [leaf 6]

myTree1 = t0
    where
        leaf i = Node CustomNode{identifier = i} []
        t0 = Node CustomNode{identifier = 7} [leaf 8]

deleteNode :: Int -> [CustomTree] -> [CustomTree]
deleteNode _ [] = []
deleteNode n (x:xs) = if isNodeInTree n x then deleteNodeFromTree n x ++ xs else deleteNode n xs
--below is the fixed line as per the answer below
--deleteNode n (x:xs) = if isNodeInTree n x then deleteNodeFromTree n x ++ xs else x : deleteNode n xs

deleteNodeFromTree :: Int -> CustomTree -> [CustomTree]
deleteNodeFromTree n (Node c xs) = if identifier c == n then [] else deleteNode n xs
--below is the fixed line as per the answer below
--deleteNodeFromTree n (Node c xs) = if identifier c == n then xs else deleteNode n xs

isNodeInTree :: Int -> CustomTree -> Bool
isNodeInTree n (Node c xs) = if identifier c == n then True else isNodeInForest n xs

isNodeInForest :: Int -> [CustomTree] -> Bool
isNodeInForest n [] = False
isNodeInForest n (x:xs) = if isNodeInTree n x then True else isNodeInForest n xs

Any help would be much appreciated!

Upvotes: 4

Views: 1154

Answers (1)

MathematicalOrchid
MathematicalOrchid

Reputation: 62808

It looks like you've made a reasonable start here.

I'm presuming you hope for deleteNode to take a forest and return that same forest, but with the specified node removed. In that case,

if isNodeInTree n x then ... else deleteNode n xs

you just threw x away. You probably didn't mean to do that.

... else x : deleteNode n xs

would keep that tree in the forest, which is probably what you intended.

Also, in deleteNodeFromTree:

if identifier c == n then [] ...

Perhaps you wanted to return all the children of the node at this point? (So they all become root nodes.)

Those are the only things that stand out to me. See where that takes you...

Upvotes: 5

Related Questions