从 f# 中字符串列表的给定路径创建树

Question

我有一个类型定义：

type FsTree = Node of (string * FsTree) list

我创建一个空节点：

let createEmptyFsTree () : FsTree = Node[]

我想从字符串列表的路径构建一棵树，例如：

let fs1 = create ["MainNode";"nodeA";"nodeB"] (createEmptyFsTree())
let fs2 = create ["MainNode";"nodeC";"nodeD"] fs1
let fs3 = create ["MainNode";"nodeC";"nodeE"] fs2

结果将是：

Node [("MainNode", Node [

                             ("nodeA", Node [("nodeB", Node [])]);
                             ("nodeC", Node [
                                         ("nodeD", Node[]);
                                         ("nodeE", Node[])])])]

到目前为止，这是我的代码。我被困了2天。请帮忙。

let create (p : string list) (fs : FsTree) =
        let rec create (p : string list) (fs : FsTree) =
            match fs with 
            | Node n -> match p, n with
                        | h :: t, (name, rsNode) :: rsTree when name = h -> Node([(h, (create t rsNode))] @ rsTree)
                        | _, lNode :: rsTree -> Node([lNode]@rsTree)
                        | h :: t, [] -> Node ([h, (create t (createEmptyFsTree()))])
                        | [],[] -> Node[]
        create p fs

我只能从第一个路径创建树：

Node [("MainNode", Node [("nodeA", Node [("nodeB", Node [])])])]

Answer 1

这道题的难点在于有几个结构（路径是一个list，每个节点是一个list和一个子树）需要同时递归遍历为了让它工作。仅在一个函数中这样做变得很难理解。

这就是为什么我喜欢通过将问题分解成更小的部分来简化问题。这里我们将使用 2 个相互递归的函数（注意语法）。首先，我将重命名函数，以便更好地理解它们的作用。我还避免为函数和变量重复相同的名称，因为这会造成混淆。我的第一个函数只会处理遍历路径 p:

let rec addPath (p : string list)   (Node ns) =
    match p with
    | []       -> Node                    ns
    | hp :: tp -> Node (addHeadPath hp tp ns)

我在第二个参数(Node ns)上使用模式匹配来获取子节点列表，这是因为下一个函数将遍历该列表。

在我的 match 表达式中，我喜欢首先处理递归结束的空列表情况。第二种情况，将头尾分开，交给另外一个函数处理：

and addHeadPath hp tp ns =
    match ns with
    | []                          -> [hp, addPath tp (Node[]) ]
    | (nn, st) :: tn when nn = hp -> (nn, addPath tp st       ) ::                   tn
    | hn       :: tn              -> hn                         :: addHeadPath hp tp tn

addHeadPathTo 与 addPathTo 相互递归，因此我将它们与 and 联系在一起，而不是另一个 let rec。

同样首先处理空情况，returns 一个包含一个节点的列表，然后调用 addPathTo 添加路径的其余部分。第二种情况是当节点已经存在时，在这种情况下我们将路径的其余部分添加到子树 st。第三种情况通过递归调用自身不断查看节点列表。

你这样调用它：

createEmptyFsTree()
|> addPath ["MainNode";"nodeA";"nodeB"] 
|> addPath ["MainNode";"nodeC";"nodeD"]
|> addPath ["MainNode";"nodeC";"nodeE"]    
|> printfn "%A"

从 f# 中字符串列表的给定路径创建树

Creating tree from given path of string list in f#

filesystems

tree

f#