एफ #

Question

में मल्टीवे ट्री पर मोड़/रिकर्सन मैं मल्टीवे पेड़ के लिए आवेदन करने के लिए ब्रायन के पेड़ के लिए ब्रायनरी पेड़ (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/) को अनुकूलित करने की कोशिश कर रहा हूं।

ब्रायन के ब्लॉग से सारांश:

डाटा संरचना:

type Tree<'a> = 
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a> 
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)), 
        Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf))) 

बाइनरी ट्री तह समारोह

let FoldTree nodeF leafV tree = 
    let rec Loop t cont = 
     match t with 
     | Node(x,left,right) -> Loop left (fun lacc ->  
           Loop right (fun racc -> 
           cont (nodeF x lacc racc))) 
     | Leaf -> cont leafV 
    Loop tree (fun x -> x) 

उदाहरण

let SumNodes = FoldTree (fun x l r -> x + l + r) 0 tree7 
let Tree6to0 = FoldTree (fun x l r -> Node((if x=6 then 0 else x), l, r)) Leaf tree7 

मल्टीवे ट्री संस्करण[नहीं (पूरी तरह से) काम कर]:

डेटा संरचना

type MultiTree = | MNode of int * list<MultiTree> 

let Mtree7 = MNode(4, [MNode(2, [MNode(1,[]); MNode(3, [])]); 
        MNode(6, [MNode(5, []); MNode(7, [])])]) 

तह समारोह

let MFoldTree nodeF leafV tree = 
    let rec Loop tree cont = 
     match tree with 
     | MNode(x,sub)::tail -> Loop (sub@tail) (fun acc -> cont(nodeF x acc)) 
     | [] -> cont leafV 
    Loop [tree] (fun x -> x) 

उदाहरण 1 रिटर्न 28 - मैंने सोचा था कि MFoldTree कहीं एक map.something जरूरत थी लेकिन मुझे मिल गया काम करने के लिए

let MSumNodes = MFoldTree (fun x acc -> x + acc) 0 Mtree7 

उदाहरण 2

नहीं चलता है

let MTree6to0 = MFoldTree (fun x acc -> MNode((if x=6 then 0 else x), [acc])) Mtree7 

शुरू में लगता है यह इसके बजाय @ ऑपरेटर के साथ काम करने के लिए।

दूसरे उदाहरण पर कोई मदद और MFoldTree फ़ंक्शन में मैंने जो किया है उसे ठीक करने के लिए बहुत अच्छा होगा!

चीयर्स

dusiod

Answer 1

एक अन्य समाधान हो सकता है

let rec mfold f a (MNode(x,s)) = f (List.fold (fun a t -> mfold f a t) a s) x 

वास्तव में, हम पेड़ एक नज़दीकी struct के रूप में (यह गुना करने के लिए) का इलाज कर सकते हैं: प्रारंभिक मूल्य एक खाली पेड़ से उत्पादित एक खाली सूची है। (

> mfold (fun a x -> if x = 6 then a else x + a) 0 Mtree7;; 
val it : int = 22 

कि समारोह सामान्य हो सकता है List.fold, Array.fold के रूप में, ...:

मामले उपयोग

> mfold (+) 0 Mtree7;; 
val it : int = 28 

फ़िल्टर सामान्य गुना के साथ एक ही है (क्योंकि mfold एक सामान्य गुना है) जेनेरिक हो सकता है)।

"लेकिन दूसरे के इरादे ताकि किसी भी नोड्स जो उदाहरण के लिए मान 6 था अब मान 0 है पूरे वृक्ष संशोधित वापस जाने के लिए है" लेकिन यह एक fold गणना नहीं है, एक है map!

आप (एक नज़दीकी struct के रूप में, इलाज फिर से,) easilly कर सकते हैं

let rec mmap f (MNode(x,s)) = MNode(f x, List.map (mmap f) s) 

मामले

> mmap (fun x -> if x=6 then 0 else x) Mtree7;; 
val it : MultiTree = 
    MNode 
    (4, 
    [MNode (2,[MNode (1,[]); MNode (3,[])]); 
     MNode (0,[MNode (5,[]); MNode (7,[])])]) 

फिर से उपयोग, मैं हर संभव सूची कंटेनर (Seq के लिए यह करने के लिए सुझाव देते हैं, List , Array, ...), यह उपयोगकर्ता को संदर्भ में सर्वोत्तम रणनीति का चयन करने में सक्षम बनाता है।

नोट्स:

• मैं एफ # में नए हूँ, मुझे क्षमा करें यदि कुछ गलत है।
• ढेर का आकार कोई समस्या नहीं होनी चाहिए, ढेर का स्तर पेड़ के गहरे के बराबर है।

Answer 2

चाल है कि आप गुना करने के लिए एक अतिरिक्त समारोह पारित करने के लिए की जरूरत है।

ब्रायन के संस्करण में, गुना फ़ंक्शन केवल nodeF लेता है जिसे नोड में मान और बाएं और दाएं उप-पेड़ से उत्पादित दो मानों के साथ बुलाया जाता है।

यह मल्टीवे पेड़ों के लिए पर्याप्त नहीं है। यहां, हमें एक फ़ंक्शन nodeF की आवश्यकता है जिसे नोड में मान और उप-पेड़ों के सभी मानों को एकत्रित करके उत्पादित किया जाता है। लेकिन आपको एक फ़ंक्शन की भी आवश्यकता है - combineF कहें जो नोड के एकाधिक उप-पेड़ से उत्पादित मूल्य को जोड़ती है।

आपका गुना समारोह एक अच्छी शुरुआत है - तुम सिर्फ tail कार्रवाई करने के लिए एक और पुनरावर्ती कॉल जोड़ने की जरूरत है: क्योंकि हम सिर्फ दोनों कार्यों के लिए + ऑपरेटर का उपयोग,

let MFoldTree nodeF combineF leafV tree = 
    let rec Loop trees cont = 
     match trees with 
     | MNode(x,sub)::tail -> 
      // First, process the sub-trees of the current node and get 
      // a single value called 'accSub' representing (aggregated) 
      // folding of the sub-trees. 
      Loop sub (fun accSub -> 
       // Now we can call 'nodeF' on the current value & folded sub-tree 
       let resNode = nodeF x accSub 
       // But now we also need to fold all remaining trees that were 
       // passed to us in the parameter 'trees'.. 
       Loop tail (fun accTail -> 
       // This produces a value 'accTail' and now we need to combine the 
       // result from the tail with the one for the first node 
       // (which is where we need 'combineF') 
       cont(combineF resNode accTail))) 
     | [] -> cont leafV 
    Loop [tree] (fun x -> x) 

संक्षेप आसान है:

let MSumNodes = MFoldTree (+) (+) 0 Mtree7 

पेड़ को फ़िल्टर करना अधिक मुश्किल है। nodeF फ़ंक्शन नोड में तत्व और सूची बाल नोड्स (जो एकत्रीकरण का परिणाम है) प्राप्त करेगा और एकल नोड का उत्पादन करेगा। combineF फ़ंक्शन को पहले नोड (जो MultiTree मान है) और शेष नोड्स से उत्पादित बच्चों की एक सूची से परिणाम प्राप्त होगा।

let MTree6to0 = 
    MFoldTree (fun x children -> MNode((if x=6 then 0 else x), children)) 
      (fun head tail -> head::tail) [] Mtree7