在树中搜索和替换

Question

我想在树中进行搜索和替换，搜索一个子树并将其替换为另一个：

type Tree =
    | A of string
    | B of int
    | C of List<Tree>

let rec replace search repl subject =
    if subject = search then
        repl
    else
        match subject with
            | C l -> C (l |> List.map (replace search repl))
            | _ -> subject

是否有更简单或更通用的方法来执行此操作和类似的转换（例如包含）？它似乎非常适合 fmap (Haskell)，但我无法让它工作。

Answer 1

这个函数对我来说看起来很易读。可以这样缩短：

let rec replace search repl = function
    | x when x = search -> repl
    | C l -> List.map (replace search repl) l |> C
    | x -> x

与 contains 看起来非常相似。

为了提高通用性，您可以尝试检查树数据结构和树内容的可区分联合是否可以是单独的类型，从而允许将数据类型化为MyTree<MyContent>。这可能适用于也可能不适用于问题，但在适用的情况下，拆分容器和内容会大大提高可重用性和可读性。

对于通用 MyTree<'T> = Leaf of 'T | Branch of MyTree<'T> list，检查节点（分支或叶）的时间不会太长：

let rec containsNode node = function
    | Leaf _ as x -> x = node
    | Branch l as b -> b = node || List.exists (containsNode node) l

也不是替换任何节点的函数:

let rec replaceNode node newNode = function
    | x when x = node -> newNode
    | Branch l -> List.map (replaceNode node newNode) l |> Branch
    | Leaf _ as x -> x

换句话说，简约类型和模式匹配可以很好地解决这类问题。 尽管并非总是如此。如果不适用，请不要介意post。

在树中搜索和替换

Search & Replace in tree

f#

functional-programming