从 Haskell 中的玫瑰树中删除一个元素

Question

我试图通过给出节点父节点的名称和节点名称来从 Haskell 中的玫瑰树中删除一个元素：

我写了这个但是编译不了

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

错误是：

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.

我对玫瑰树的定义如下

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

如何让它工作以及return一个不包含指定元素的新树？

Answer 1

我不清楚你为什么需要这里的 parent。您可以将视图实现为：

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

如果我们因此找到了项目 (x == x')，那么我们 return Empty，否则我们在叶子上递归。

请注意，此函数将删除 all 个以 x 作为“标签”的分支，因此如果有多个目录 foo/，它将删除所有这些。

如果 parent 是 parent 节点的名称，您可以使用：

deleteNode :: Eq a => a -> a -> Rose a -> Rose a
deleteNode _ _ Empty = Empty
deleteNode parent x (Branch x' trees) 
  | <strong>parent == x'</strong> = 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

这将删除所有具有作为父级标签 Branch 值 parent 和 x 作为自身值的项目。然而，树中仍然可以有多个项目以 foo 作为父级，bar 作为标签，这样这些项目将所有被删除。

从 Haskell 中的玫瑰树中删除一个元素

Deleting an element from a rose tree in Haskell

tree

haskell