Fsharp / как изменить тип Node of (string * FsTree) списка в список, где 2 пути не могут быть идентичными

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 поэтому легко думать о них так, как будто они могут быть только одной функцией.

Ото, processList является двойной рекурсивной Он вызывает себя, чтобы пройти через элементы списка, и он вызывает processNode углубиться в поддерево.

Существует также параметр аккумулятора, который необходимо передать, который prepend который несет путь.