搜索和樹

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 

換句話說，簡約類型和模式匹配可以很好地解決這類問題。 雖然他們並不總是。如果不適用，請不要介意這篇文章。