F #: arbre récursif

Question

J'ai un XElement à peu près fait comme ceci:

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

chaque tâche élément a un identifiant unique, certaines informations que je ne suis pas de rapports et un ID parent. L'identifiant parent fait référence à une autre tâche de sorte qu'il est possible de représenter un arbre.

J'ai déjà une fonction C# pour trier cette 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); 
     } 
    } 

Ici je continue d'invoquer récursive la fonction de recherche des enfants des éléments de chaque nœud et en ajoutant la nouvelle à un XElement appelé taskOutput. Chaque fois que je passe une référence à ce nouvel objet, l'id de l'élément courant (qui représente le parent dans l'appel suivant) et le XElement original avec toutes les tâches.

Maintenant, je pensais que ce serait un bon cas de test pour apprendre un peu sur F # simplement réécrire cette chose d'une manière fonctionnelle, mais j'ai des problèmes avec elle.

C'est ce que je suis arrivé à ce jour:

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) 

Il ne compile pas spécifier que le type de retour pour let (en let children) a une erreur.

Une aide pour que je comprenne mieux? Merci beaucoup

Answer 1

Voici une version basée sur le vôtre qui semble faire une sorte de travail topologique des éléments enfants. Cependant, j'imagine qu'il y a un moyen beaucoup plus simple; je cherche maintenant ...

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

Votre fonction doSort ne renvoie rien. (Pas même un unit, qui est l'équivalent d'une méthode void en C#). Ce n'est pas juste de définir des variables dans une fonction dans F #.

En outre, je ne suis pas sûr que vous vouliez réellement attribuer quelque chose à la variable children, puisque vous ne l'utilisez pas du tout. Essayez de changer la fonction doSort à ceci:

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

Ok, voici un topological sort générique 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 

et voici vos données

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

ensuite d'appliquer la TopoSort à ce problème , vous l'avez où le noeud '0' est implicitement la 'racine', donc nous pouvons écrire

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

et obtenir le résultat souhaité:

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

Answer 4

Il est un ancien poste, mais n'a pas vu quoi que ce soit pour répondre à la question de débordement de pile.

Pour quiconque se demandant, vous pouvez éviter les débordements de pile en utilisant la récursion de la queue. Assurez-vous que vos appels récursifs sont les dernières opérations effectuées par votre fonction, comme à la fin du match ou si des branches, la fin même de la fonction, etc.

Veillez à ne pas utiliser le résultat de l'appel récursif de quelque manière, la forme ou la forme, y compris « num + (recCall val) », comme qui exige l'exécution de revenir en arrière à la fonction d'origine pour effectuer la somme. C'est ce saut, ou plus exactement, se souvenir quand et où aller, qui déborde de la pile, et s'il n'y a rien à faire et à faire, le compilateur est libre de faire disparaître le surcoût ajouté.

C'est l'une des raisons pour lesquelles tant de fonctions Seq et List (telles que Seq.unfold) nécessitent des paramètres accumulator/state. Il vous permet d'effectuer des opérations en toute sécurité sur les résultats de la récursion précédente, en le gérant au début de l'appel suivant.

ex:

débordera en position de queue: num + (recCall val)

ne déborde pas en position de queue: (recCall num val)