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)