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는 트리를 나타낼 수 있도록 다른 타스크를 참조합니다. 여기

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를에 추가 재귀 적으로 함수를 호출 유지 :

는 이미이 구조를 정렬하는 C#을 기능을 가지고있다. 이 새 객체에 대한 참조를 전달할 때마다 현재 요소의 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

그것은 이전 게시물입니다하지만 스택 오버플로 문제를 해결하기 위해 아무것도 보지 않았다 있습니다.

궁금한 분은 꼬리 재귀를 사용하여 스택 오버플로를 피할 수 있습니다. 재귀 호출이 일치 작업이 끝나거나 분기, 함수의 맨 끝 등과 같이 함수가 수행 한 마지막 작업인지 확인하십시오.

하는 것은 조심하지 않는 것이가를 수행하기 위해 원래의 함수로 다시 이동하려면 실행을 필요로 사용을 포함하여 어떤 방식으로, 모양이나 형태의 재귀 호출의 결과 "NUM + (recCall 발)"에 합집합. 스택을 오버플로하는 점프와 점프를 기억하고, 돌아올 것도없고 돌아갈 것도 없다면 컴파일러는 추가 된 오버 헤드를 없앨 수 있습니다.

이렇게 많은 Seq 및 List 함수 (예 : Seq.unfold)가 누적 기/상태 매개 변수를 필요로하는 이유 중 하나입니다. 이 기능을 사용하면 이전 재귀 결과를 다음 호출 시작시 처리하여 안전하게 수행 할 수 있습니다.

예 :

꼬리 위치에 오버플로 : num + (recCall val)

것이다 꼬리 위치에 있지 오버 플로우 : (recCall num val)