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

Question

In FSharp, I would like to do the following

given a type : type FsTree = Node of (string * FsTree) list

I would like to define a predicate toStringList so that : toStringList myFsTree gives the bellow result

result :

[
    ["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"];
]

Where

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 [])
]

What I have done so far (here below) is absolutely not correct, I know that. But I'm really stuck here! Does anyone have an idea what to do?

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

Answer 1

This is a tricky one because it requires 2 mutually recursive functions one for Node and one for the list inside 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

You need one recursive function to go over the elements in the list: processList

and another one to go over the subnodes in the list: processNode.

The confusion arises because all processNode does is get the list from Node and then call processList so it is easy to think of them as if they could be just one function.

OTOH, processList is double recursive. It calls itself to go over the elements of the list and it calls processNode to go deeper into the subtree.

There is also an accumulator parameter that needs to be passed which is prepend which carries the path.