एफ # एक पेड़

Question

मैं की tuples पूर्णांक * स्ट्रिंग एक सूची है करने के लिए सूची को बदलने जहां पूर्णांक स्तर है और स्ट्रिंग नाम

let src = [ 
     (0, "root"); 
      (1, "a"); 
       (2, "a1"); 
       (2, "a2"); 
      (1, "b"); 
       (2, "b1"); 
        (3, "b11"); 
       (2, "b2"); 
     ] 

है और मैं इसे

let expectingTree = 
    Branch("root", 
    [ 
     Branch("a", 
      [ 
       Leaf("a1"); 
       Leaf("a2") 
      ]); 
     Branch("b", 
      [ 
       Branch("b1", [Leaf("b11")]); 
       Leaf("b2") 
      ]); 
    ]); 

निम्नलिखित नीचे करने के लिए बदलने की जरूरत है जिस तरह से मैंने इसे किया, लेकिन क्या कोई इसे हासिल करने के बेहतर तरीके से सलाह दे सकता था। मैं एफ # के लिए नया हूं, और सी # कोड एक ही काम करने के लिए कुछ छोटा होगा, इसलिए मुझे लगता है कि मैं इसे गलत कर रहा हूं। सब से

type Node = 
    | Branch of (string * Node list) 
    | Leaf of string 

let src = [ 
      (0, "root"); 
       (1, "a"); 
        (2, "a1"); 
        (2, "a2"); 
       (1, "b"); 
        (2, "b1"); 
         (3, "b11"); 
        (2, "b2"); 
      ] 

let rec setParents (level:int) (parents:list<int>) (lst:list<int*int*string>) : list<int*int*string> = 
    //skip n items and return the rest 
    let rec skip n xs = 
     match (n, xs) with 
     | n, _ when n <= 0 -> xs 
     | _, [] -> [] 
     | n, _::xs -> skip (n-1) xs 

    //get parent id for given level 
    let parentId (level) = 
     let n = List.length parents - (level + 1) 
     skip n parents |> List.head 

    //create new parent list and append new id to begin 
    let newParents level id = 
     let n = List.length parents - (level + 1) 
     id :: skip n parents 

    match lst with 
    | (id, l, n) :: tail -> 
         if l = level then (id, parentId(l), n) :: setParents l (newParents l id) tail 
         elif l <= level + 1 then setParents l parents lst 
         else [] //items should be in order, e.g. there shouldnt be item with level 5 after item with level 3 
    | _ -> [] 


let rec getTree (root:int) (lst: list<int*int*string>) = 

    let getChildren parent = 
     List.filter (fun (_, p, _) -> p = parent) lst 

    let rec getTreeNode (id:int) (name:string) = 
     let children = getChildren id 
     match List.length children with 
     | 0 -> Leaf(name) 
     | _ -> Branch(name, 
         children 
         |> List.map (fun (_id, _, _name) -> getTreeNode _id _name)) 

    match getChildren root with 
    | (id, _, n) :: _ -> getTreeNode id n 
    | _ -> Leaf("") 

let rec printTree (ident:string) (tree:Node) = 
    match tree with 
    | Leaf(name) -> 
     printfn "%s%s" ident name 
    | Branch(name, children) -> 
     printfn "%s%s" ident name 
     List.iter (fun (node) -> printTree (" " + ident) node) children 

let tree = 
    src 
    |> List.mapi (fun i (l, n) -> (i+1, l, n)) //set unique id to each item 
    |> setParents 0 [0] //set parentId to each item 
    |> getTree 0 


printTree "" tree 

Console.ReadKey() |> ignore 

Answer 1

सबसे पहले, आप वास्तव में यदि आपके शाखा उप पेड़ की एक सूची से युक्त है Leaf के लिए एक प्रतिष्ठित मामला है, क्योंकि पत्ती बस कोई उप पेड़ के साथ एक शाखा है की जरूरत नहीं है।

type Tree = 
    | Branch of string * list<Tree> 

एक पेड़ से सूची मोड़ के लिए मुख्य कार्य शायद स्पष्ट पुनरावर्ती सूची प्रक्रिया का प्रयोग होता लागू करना आसान है: तो, मैं निम्नलिखित पेड़ प्रकार का उपयोग करने जा रहा हूँ। आप इसे एक पास में कर सकते हैं - बस तत्वों पर जाएं और जब भी आपको नेस्टेड इंडेक्स मिल जाए (या जब आप एक छोटी अनुक्रमणिका प्राप्त करते हैं तो रिकर्सिव कॉल की उचित संख्या से वापस आएं)। यह मेरा प्रयास है:

/// Build a tree from elements of 'list' that have larger index than 'offset'. As soon 
/// as it finds element below or equal to 'offset', it returns trees found so far 
/// together with unprocessed elements. 
let rec buildTree offset trees list = 
    match list with 
    | [] -> trees, [] // No more elements, return trees collected so far 
    | (x, _)::xs when x <= offset -> 
     trees, list // The node is below the offset, so we return unprocessed elements 
    | (x, n)::xs -> 
     /// Collect all subtrees from 'xs' that have index larger than 'x' 
     /// (repeatedly call 'buildTree' to find all of them) 
     let rec collectSubTrees xs trees = 
     match buildTree x [] xs with 
     | [], rest -> trees, rest 
     | newtrees, rest -> collectSubTrees rest (trees @ newtrees) 
     let sub, rest = collectSubTrees xs [] 
     [Branch(n, sub)], rest 

समारोह में प्रारंभिक ऑफसेट और पेड़ एकत्र हुए हैं। trees पैरामीटर हमेशा [] होने जा रहा है और आपको प्रारंभिक offset के लिए कुछ मूल्य चाहिए। परिणाम दिए गए स्तर से नीचे के पेड़ की एक सूची है और शेष तत्वों की एक सूची है:

let res = buildTrees -1 [] src 

मान लिया जाये कि जड़ -1 से ऊपर है, तो आप सिर्फ टपल के दूसरे भाग की उपेक्षा कर सकते हैं (यह खाली सूची होना चाहिए) और पहला पेड़ प्राप्त करें (केवल एक होना चाहिए):

/// A helper that nicely prints a tree 
let rec print depth (Branch(n, sub)) = 
    printfn "%s%s" depth n 
    for s in sub do print (depth + " ") s 

res |> fst |> Seq.head |> print ""