0

在 FSharp 中，我想做以下事情

给定一个类型： type FsTree = Node of (string * FsTree) list

我想定义一个谓词 toStringList 以便： toStringList myFsTree给出以下结果

结果 ：

[
    ["n1"];
    ["n2"; "sub_n2_1"];
    ["n2"; "sub_n2_2"];
    ["n3"; "sub_n3"; "sub_sub_n3_1"];
    ["n3"; "sub_n3"; "sub_sub_n3_2"];
    ["n3"; "sub_n3"; "sub_sub_n3_3"];
    ["n4"];
]

在哪里

let myFsT = Node [
    ("n1", Node []); 
    ("n2", Node [
    ("sub_n2_1", Node []);
    ("sub_n2_2", Node [])
    ]); 
    ("n3", Node [
    ("sub_n3", Node [
    ("sub_sub_n3_1", Node []); 
    ("sub_sub_n3_2", Node []); 
    ("sub_sub_n3_3", Node []); 
    ])
    ]); 
    ("n4", Node [])
]

我到目前为止所做的（如下）绝对不正确，我知道。但我真的被困在这里了！有谁知道该怎么做？

let rec test (fst:FsTree) = 
        match fst with
        | Node []              -> []
        | Node ((str, subFst)::restNode) -> 
            [[str] @ (test subFst)] @ (test restNode)
4

1 回答 1

2

这是一个棘手的问题，因为它需要 2 个相互递归的函数Node，一个用于内部列表，一个用于内部列表Node。

let rec processNode     prepend node =
    let rec processList prepend listOfNodes =
        match   listOfNodes with
        | []                         -> []
        | (str, subNode) :: restList -> 
            let restList = processList  prepend restList
            let newPrepend = List.append prepend [ str ]
            match processNode newPrepend subNode with
            | []  -> [ newPrepend ]
            | lst -> lst
            @ restList
    match node with Node listOfNodes -> processList prepend listOfNodes

processNode [] myFsT
|> List.iter print

您需要一个递归函数来遍历列表中的元素：processList

另一个遍历列表中的子节点：processNode.

之所以会产生混淆，是因为processNode所做的只是从中获取列表Node然后调用processList，因此很容易将它们想象成它们可能只是一个函数。

OTOH，processList是双递归的。它调用自己来遍历列表的元素，并调用processNode更深入的子树。

还有一个累加器参数需要传递，prepend它携带路径。

于 2018-11-29T05:34:47.227 回答