F#: Recursive tree

Question

I have a XElement roughly done like this:

<Tasks>
  <Task>
    <Parent>0</Parent>
    <Id>1</Id>
  </Task>
  <Task>
    <Parent>1</Parent>
    <Id>2</Id>
  </Task>
  <Task>
    <Parent>1</Parent>
    <Id>3</Id>
  </Task>
  <Task>
    <Parent>3</Parent>
    <Id>5</Id>
  </Task>
  [..]

Each Task Element has a unique Id, some informations I'm not reporting and a parent id. The parent id refers to another task so that it is possible to represent a tree.

I already have a C# function to sort this structure:

    private void SortTask(ref XElement taskOutput, XElement tasks, string parent)
    {
        var children = from t in tasks.Elements("Task")
                       where t.Element("Parent").Value == parent
                       select t;

        foreach (XElement task in children.AsEnumerable())
        {
            taskOutput.Add(task);
            SortTask(ref taskOutput, tasks, task.Element("Id").Value);
        }
    }

Here I keep invoking recursively the function searching the children elements of each node and adding the to a new XElement called taskOutput. Each time I pass a reference to this new object, the id of the current element (that represent the parent in the next call) and the original XElement with all the tasks.

Now, I thought this would be a good test case to learn a bit about F# simply rewriting this thing in a functional way, but I'm having trouble with it.

This is what I got so far:

type TaskManager(taskListXml) = 
    member o.taskList = XElement.Parse(taskListXml).Elements(XName.op_Implicit("Task"))

    member o.Sort =
        let parent =
            o.taskList
            |> Seq.find (fun t -> t.Element(XName.op_Implicit("Parent")).Value.Equals("0"))
        let rec doSort t =
            let parId = t.Element(XName.op_Implicit("Id")).Value
            let children = 
                o.tasklist
                |> Seq.filter (fun x -> x.Element(XName.op_Implicit("Parent")).Value.Equals(parId))
                |> Seq.iter (fun x -> Console.WriteLine(x))
                |> Seq.iter (fun x -> doSort x)

It does not compile specifying that the return type for let (in let children) has an error.

Any help in let me understand this better? Thank you very much

Answer 1

It's an old post but didn't see anything to address the stack overflow question.

For anyone wondering, you can avoid stack overflows by using tail recursion. Make sure your recursive calls are the last operations performed by your function, such as at the end of match or if branches, the very end of the function, etc.

Be careful not to use the result of the recursive call in any way, shape, or form, including "num + (recCall val)," as that requires execution to jump back to the original function to perform the sum. It's that jump, or more appropriately, remembering when and where to jump to, which overflows the stack, and if there is nothing to come back and do, the compiler is free to do away with the added overhead.

This is one of the reasons why so many Seq and List functions (such as Seq.unfold) require accumulator/state parameters. It allows you to safely perform operations on the results of previous recursion, by handling it at the beginning of the next call.

ex:

will overflow in tail position: num + (recCall val)

will not overflow in tail position: (recCall num val)

Answer 2

Ok, here's a generic topological sort in F#:

// 'parent x y' means y is a child of x
let TopoSort parent s =
    let a = Seq.to_array s
    let visited = Array.create (a.Length) false
    let result = new ResizeArray<_>()
    let rec visit i =
        if not visited.[i] then
            visited.[i] <- true
            result.Add a.[i]
            for j in 0 .. a.Length - 1 do
                if parent a.[i] a.[j] then
                    visit j
    for j in 0 .. a.Length - 1 do
        visit j
    result

and here's your data

open System.Xml.Linq 
let xn s = XName.op_Implicit s
let xmlString = @"
    <Tasks>
      <Task>
        <Parent>3</Parent>
        <Id>5</Id>
      </Task>
      <Task>
        <Parent>1</Parent>
        <Id>2</Id>
      </Task>
      <Task>
        <Parent>0</Parent>
        <Id>1</Id>
      </Task>
      <Task>
        <Parent>1</Parent>
        <Id>3</Id>
      </Task>
    </Tasks>"
let taskXEs = XElement.Parse(xmlString).Elements(xn("Task"))

Then to apply the TopoSort to this problem, you have it where node '0' is implicitly the 'root', so we can write

let result = new XElement(xn("Tasks"))
taskXEs 
// prepend faux '0' element to 'root' the toposort
|> Seq.append (Seq.singleton(XElement.Parse("<Task><Parent/><Id>0</Id></Task>")))
|> TopoSort (fun x y -> 
    y.Element(xn("Parent")).Value.Equals(x.Element(xn("Id")).Value))
// remove the faux element
|> Seq.skip 1
|> Seq.iter (fun n -> result.Add(n))

and get the desired result:

printfn "%s" (result.ToString())

Answer 3

Here's a version based on yours that seems to do a working topological sort of the child elements. However I imagine there's a much simpler way; am looking for that now...

open System.Xml.Linq 

let xmlString = @"
    <Tasks>
      <Task>
        <Parent>3</Parent>
        <Id>5</Id>
      </Task>
      <Task>
        <Parent>1</Parent>
        <Id>2</Id>
      </Task>
      <Task>
        <Parent>0</Parent>
        <Id>1</Id>
      </Task>
      <Task>
        <Parent>1</Parent>
        <Id>3</Id>
      </Task>
    </Tasks>
"

let xn s = XName.op_Implicit s

type TaskManager(taskListXml) =     
    member o.taskList = XElement.Parse(taskListXml).Elements(xn("Task"))
    member o.Sort() =
        let xResult = new XElement(xn("Tasks"))
        let parent =
            o.taskList
            |> Seq.find (fun t -> t.Element(xn("Parent")).Value.Equals("0"))
        let rec doSort (t:XElement) =
            let parId = t.Element(xn("Id")).Value
            o.taskList 
            |> Seq.filter (fun x -> x.Element(xn("Parent")).Value.Equals(parId))
            |> Seq.iter (fun x -> 
                xResult.Add(x)
                doSort x
                )
        doSort parent
        xResult

let tm = new TaskManager(xmlString)
let r = tm.Sort()
printfn "%s" (r.ToString())

Answer 4

Your doSort function doesn't return anything. (Not even a unit, which is the equivalent to a void method in C#). It is not valid just to define variables in a function in F#.

Moreover, I'm not sure you actually want to assign anything to the children variable, since you're not at all using it. Try changing the doSort function to this:

let rec doSort t =
    let parId = t.Element(XName.op_Implicit("Id")).Value
    o.tasklist
        |> Seq.filter (fun x -> x.Element(XName.op_Implicit("Parent")).Value.Equals(parId))
        |> Seq.iter (fun x -> Console.WriteLine(x))
        |> Seq.iter (fun x -> doSort x)