F＃：递归树

Question

我有这样大致做了的XElement：

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

每个任务元素都有唯一的ID，一些信息，我不报告和父ID。父id引用另一个任务，以便可以表示一棵树。

我已经有一个C＃的功能进行排序这样的结构：

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); 
     } 
    } 

这里我把递归调用该函数搜索每个节点的子元素，并加入到一个名为taskOutput新的XElement。每次我传递一个对这个新对象的引用时，当前元素的id（代表下一次调用中的父元素）以及包含所有任务的原始XElement。

现在，我认为这将是一个很好的测试案例来学习一些关于F＃的简单重写这个东西的功能，但我遇到了麻烦。

这是我走到这一步：

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) 

这并不编译指定为让返回类型（在let children）有错误。

任何帮助让我更好地理解这一点？ 非常感谢你

Answer 1

下面是基于你的版本似乎做工作拓扑排序的子元素。不过，我想有一个更简单的方法;在寻找，现在...

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 2

你的doSort函数不返回任何东西。 （甚至不是unit，这相当于C＃中的void方法）。仅仅在F＃中的函数中定义变量是无效的。此外，我不确定你是否真的想要分配任何东西给children变量，因为你根本没有使用它。尝试改变doSort功能如下：

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) 

Answer 3

好吧，这里是在F＃通用topological sort：

// '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 

，这里是你的数据

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

然后到TopoSort适用于这个问题，你有它在节点'0'隐含'根'，所以我们可以写

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

，并得到想要的结果：

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

Answer 4

这是一个老的文章，但没有看到任何东西，以解决堆栈溢出问题。

对于任何人想知道的，你可以通过使用尾递归来避免堆栈溢出。确保递归调用是您的函数执行的最后一个操作，例如匹配结束或分支，函数的最后一个等等。

要小心，不要使用以任何方式，形状或形式的递归调用，包括结果“数+（recCall VAL），”作为需要执行跳回原来的函数来执行和。正是这种跳跃，或者更恰当地说，记住何时何地跳转到堆栈溢出，如果没有东西可以回来，编译器可以自由地消除额外的开销。

这是为什么如此多的Seq和List函数（如Seq.unfold）需要累加器/状态参数的原因之一。它允许您安全地对先前的递归结果执行操作，在下次调用开始时处理它。

例如：

将溢出的末尾位置：num + (recCall val)

将在尾部位置不溢出：(recCall num val)