परिसर निरंतरता

Question

निरंतरता ट्यूटोरियल मैं निश्चित लंबाई निरंतरता पर हैं पा सकते हैं सब के सब (यानी आंकड़ा संरचना मदों की एक ज्ञात संख्या के रूप में यह चल जा रहा है है

मैं DepthFirstSearch Negamax (लागू करने कर रहा हूँ http: // en .wikipedia.org/wiki/Negamax) और जब तक कोड काम करता है, मैं निरंतरता

का उपयोग कर कोड को फिर से लिखने के लिए करना चाहते

कोड रहा है के रूप में

let naiveDFS driver depth game side = 
    List.map (fun x -> 
     //- negamax depth-1 childnode opposite side 
     (x, -(snd (driver (depth-1) (update game x) -side)))) 
           (game.AvailableMoves.Force()) 
    |> List.maxBy snd 



let onPlay game = match game.Turn with 
        | Black -> -1 
        | White -> 1 

///naive depth first search using depth limiter 
let DepthFirstSearch (depth:int) (eval:Evaluator<_>) (game:GameState) : (Move * Score) = 
    let myTurn = onPlay game 

    let rec searcher depth game side = 
     match depth with 
     //terminal Node 
     | x when x = 0 || (isTerminal game) -> let movescore = (eval ((),game)) |> fst 
               (((-1,-1),(-1,-1)),(movescore * side)) 
     //the max of the child moves, each child move gets mapped to 
     //it's associated score 
     | _ -> naiveDFS searcher depth game side 

जहां अद्यतन के साथ एक साथ एक gamestate अद्यतन करता है इस प्रकार है एक दिया गया कदम, eval खेल राज्य और आर मूल्यांकन करता है वृद्धिशील मूल्यांकन के लिए एक incrementer (वर्तमान में अप्रयुक्त) eturns और टर्मिनल मूल्यांकन करता है कि स्थिति एक अंत स्थिति है या नहीं।

समस्या यह है कि मुझे निरंतरता के लिए अज्ञात संख्याओं (प्रत्येक शेष सूची.मैप पुनरावृत्ति) को साइन अप करना होगा, और मैं वास्तव में ऐसा करने का एक प्रभावी तरीका नहीं समझ सकता।

चूंकि यह एक घातीय एल्गोरिथ्म है, मैं स्पष्ट रूप से (, हालांकि मेरे मस्तिष्क यह हमारी लगाने की कोशिश कर दर्द होता है तो मैं एक कुशल एक से जवाब अधिक चाहते हैं) यह संभव के रूप में कुशल रखने के लिए देख रहा हूँ

धन्यवाद

Answer 1

मुझे लगता है कि आपको ऐसा करने के लिए List.map के निरंतर-आधारित संस्करण को लागू करने की आवश्यकता होगी। map का एक मानक कार्यान्वयन (संचायक तर्क का प्रयोग करके) इस तरह दिखता है:

let map' f l = 
    let rec loop acc l = 
    match l with 
    | [] -> acc |> List.rev 
    | x::xs -> loop ((f x)::acc) xs 
    loop [] l 

आप एक तर्क के रूप में एक निरंतरता जोड़ सकते हैं और (दिलचस्प एक निरंतरता के माध्यम से वापस जाने के लिए कोड को बदलने के लिए, आप प्राप्त करेंगे तो मामले loop समारोह, जहां हम पहले एक तर्क के रूप में कुछ निरंतरता) के साथ पूंछ-कॉल का उपयोग कर f फोन में x::xs शाखा है:

let contMap f l cont = 
    let rec loop acc l cont = 
    match l with 
    | [] -> cont acc |> List.rev 
    | x::xs -> f x (fun x' -> loop (x'::acc) xs cont) 
    loop [] l cont 

तो फिर तुम सामान्य बदल सकते हैंइस तरह एक निरंतरता आधारित संस्करण में:

// Original version 
let r = List.map (fun x -> x*2) [ 1 .. 3 ] 

// Continuation-based version 
contMap (fun x c -> c(x*2)) [ 1 .. 3 ] (fun r -> ...) 

मुझे यकीन है कि अगर यह आप किसी भी उल्लेखनीय प्रदर्शन में सुधार दे देंगे नहीं हूँ। मुझे लगता है कि यदि आपके पास बहुत गहरी रिकर्सन है (जो ढेर पर फिट नहीं है) तो निरंतरता की आवश्यकता होती है। यदि यह ढेर पर फिट बैठता है, तो यह शायद ढेर का उपयोग करके तेजी से चलाएगा।

इसके अलावा, स्पष्ट निरंतरता शैली के लिए पुन: लेखन कार्यक्रम को थोड़ा बदसूरत बनाता है। आप निरंतरता के साथ काम करने के लिए गणना गणना का उपयोग कर इसे सुधार सकते हैं। ब्रायन में blog post on this very topic है।