搜索和树

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 

换句话说，简约类型和模式匹配可以很好地解决这类问题。 虽然他们并不总是。如果不适用，请不要介意这篇文章。