Remove a node from the tree and return the resulting forest

Question

I come from a Java background and want to learn some Haskell. The bit is stuck at the moment.

What I want to do: I have a list of trees, where each node has a unique identifier for all trees in the list. Now I want to remove one of the node from one of these trees and return new trees, as well as immutable trees.

Removing node should:

• make all children of the specified node become the root of the new trees
• remove the parent nodes of the remote node to the root of the node and turn it on and do the above for all the remote nodes.

Imagine the following trees:

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

Each node in the tree consists of an identifier and a list of child trees. Here is what I still have, however, obviously not working, and I'm a little lost, how can I 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 greatly appreciated!

Answer 1

Looks like you made a reasonable start here.

I assume that you are hoping deleteNodeto take the forest and return the same forest, but with the specified node removed. In this case

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

you just threw it away x. You probably did not want to do this.

... else x : deleteNode n xs

save this tree in the forest, which was probably what you intended.

In addition, in deleteNodeFromTree:

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

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

, . , ...