Fsharp / 如何将 (string * FsTree) 列表的类型节点更改为 2paths 不能相同的列表

Question

在 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)

Answer 1

这是一个棘手的问题，因为它需要 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 深入子树。

还有一个accumulator参数需要传递，就是prepend携带路径

Fsharp / 如何将 (string * FsTree) 列表的类型节点更改为 2paths 不能相同的列表

Fsharp / how to change type Node of (string * FsTree) list into a list where 2paths cannot be identical

filesystems

f#

fscheck

fsharpchart