从树中删除节点并返回生成的林

Question

我来自Java背景,想学习一些Haskell.但是,此刻有点卡住了.

我想要做的是:我有一个树列表,其中每个节点在列表中的所有树中都有唯一的标识符.现在我想删除其中一个树中的一个节点并返回新树以及未更改的树.

删除节点应该:

• 使所述节点的所有子节点成为新树的根
• 删除已删除节点的父节点直到并包括根节点,并对所有已删除的节点执行上述操作

想象一下以下树木:

当我删除节点'2'时,我希望结果是以下树:

树中的每个节点都包含标识符和子树列表.这是我到目前为止所做的,但它显然不起作用,我对如何使用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

任何帮助将非常感激!

Answer 1

看起来你在这里已经有了一个合理的开端.

我假设您希望获取deleteNode林并返回相同的林,但删除了指定的节点.在这种情况下,

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

你只是扔掉x了.你可能并不是故意这样做.

... else x : deleteNode n xs

会把那棵树留在森林里,这可能就是你想要的.

另外,在deleteNodeFromTree:

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

也许你想在此时返回节点的所有子节点？(所以他们都成了根节点.)

这些是我唯一能够脱颖而出的东西.看看你需要的地方......