f# - 如何解决 f# 树的插入功能问题

Question

拜托，我需要一些帮助来为树创建插入函数。给定字符串列表中的值应该插入到树中的每个分支和叶子中。我试图解决这个问题并得到一个非常接近的答案，但我无法正确编写函数来插入所有字符串值。

代码：

type Tree = Leaf of string | Branch of (string * Tree) list

let rec insertTree (lst : string list) (tree : Tree) : Tree =

        match lst, tree with
        | a::b::c::[], y  -> 
            match y with
            | Leaf(n) -> Branch[(a, Branch[(n, Leaf(c))])]
            | Branch[(x, p)] -> Branch[(x, Branch[(a, Branch[(b, insertTree (c::[]) p)])])]
            | _     -> insertTree (b::c::[]) y
        | _ , y    -> tree

测试：insertTree ["4"; "5";"6"] (Branch [("1", (Branch[("2", Leaf("3"))]))])

给出：Branch [("1", Branch [("4", Branch [("5", Branch [("2", Leaf "3")])])])]

我想要这个：

(Branch [("1", (Branch[("2", (Branch[("3",(Branch[("4",(Branch[("5", Leaf("6"))]))]))]))]))])

Answer 1

我将假设您只想将列表附加到最后的叶子，并且所有分支在其列表中最多只有一个元素。

let insertTree (lst : string list) (tree : Tree) : Tree =
    let rec insertSingleIntotree x t = 
        match t with
        | Leaf(n) -> Branch[(n,Leaf x)]
        | Branch[(n,p)] -> Branch[(n, insertSingleIntotree x p)]
        | _ -> failwith "no idea what should happen here!"

    lst
    |> List.fold (fun acc x -> insertSingleIntotree x acc) tree