Traverse a tree recursively and return an un-muted list of all values found? Possible?

Question

I wonder if this is even possible at all as the question suggest. My problem is that I cannot seem to grasp how to handle the fact that a given input value can have multiple children. The problem is easily solved by using the mutable SortedSet variable as shown below. But I would really like to find out if this is a problem possible to solve with pure recursion and creation of new un-muted lists or similar. I hope my question is clear. I fear I'm ignorant to the easy conclusion that it's not possible. As you can see bellow the if(true) will return a list but the else will return a list of list. So the code bellow is not in working state.

let someSet = new System.Collections.Generic.SortedSet<string>()
let rec children(value:string,listSoFar) =
    printfn "ID: %A" value 
    someSet.Add(value) works fine of course.
    let newList = List.append listSoFar [value]
    if(not (hasChildren(value))) then 
        newList
    else
        let tmpCollection = database.GetCollection<Collection>("Collection")
        let tmpQuery = Query.EQ("Field",BsonValue.Create(value))
        let tmpRes = tmpCollection.Find(tmpQuery)
        [ for child in tmpRes do
            yield children(child.Value,newList) ]


let resultList = children("aParentStartValue",[]) 
//Or do i need to use someSet values?

Answer 1

Unless the tree is very deeply nested (in which case, this would be inefficient), you can write the code as a recursive F# sequence expression that generates elements using yield and yield!

let rec children (value:string) = seq {
    // Produce the current value as the next element of the sequence
    yield value
    if hasChildren value then 
      // If it has children, then get all the children
      let tmpCollection = database.GetCollection<Collection>("Collection")
      let tmpQuery = Query.EQ("Field",BsonValue.Create(value))
      let tmpRes = tmpCollection.Find(tmpQuery)
      // For each child, generate all its sub-children recursively
      // and return all such elements as part of this sequence using 'yield!'
      for child in tmpRes do
        yield! children child.Value }

// Using 'List.ofSeq' to fully evaluate the lazy sequence
let resultList = List.ofSeq (children "aParentStartValue")

If the tree is more deeply nested, then the situation is a bit more difficult. When iterating over all the children, you'd need to pass the list collected so far to the first children, get the results and then pass the resulting list to the next children (using something like List.fold). But the above is clean and should work in most cases.