ओकैम सूची: कार्यान्वयन और नक्शा कार्यों को कार्यान्वित करें

Question

मैं वर्तमान में एक दोस्त के ओकैमल कार्यक्रम का विस्तार करने की कोशिश कर रहा हूं।

type 'a cell = Nil 
    | Cons of ('a * 'a llist) 
and 'a llist = (unit -> 'a cell);; 

मुझे लगता है कि समझ गए होंगे: यह (मेरे लिए) अजीब सूची कार्यान्वयन कुछ डेटा विश्लेषण के लिए आवश्यक कार्यों का एक विशाल संग्रह है .. जब से मैं वास्तव में एक OCaml दरार मैं वर्तमान में एक पर अटक कर रहा हूँ नहीं कर रहा हूँ यह किसी प्रकार की "आलसी" सूची लागू करता है, लेकिन मुझे बिल्कुल नहीं पता कि यह वास्तव में कैसे काम करता है। मुझे उपर्युक्त प्रकार के आधार पर एक परिशिष्ट और मानचित्र फ़ंक्शन लागू करने की आवश्यकता है। क्या किसी को यह पता चला है कि ऐसा कैसे करें?

किसी भी मदद की वास्तव में सराहना की जाएगी!

Answer 1

let rec append l1 l2 = 
    match l1() with 
     Nil -> l2 | 
     (Cons (a, l)) -> fun() -> (Cons (a, append l l2));; 

let rec map f l = 
    fun() -> 
     match l() with 
      Nil -> Nil | 
      (Cons (a, r)) -> fun() -> (Cons (f a, map f r));; 

आलसी सूचियों के इस कार्यान्वयन के मूल विचार है कि प्रत्येक गणना (तकनीकी शब्द एक बंद है) एक समारोह में समझाया गया है मज़ा के माध्यम से है() -> एक्स। एक्सप्रेशन एक्स का तब मूल्यांकन किया जाता है जब फ़ंक्शन() (इकाई मान, जिसमें कोई जानकारी नहीं है) पर लागू होता है।

Answer 2

यह ध्यान रखें कि समारोह बंद मदद कर सकता है अनिवार्य रूप से आलसी मूल्यों के बराबर हैं:

lazy n : 'a Lazy.t <=> (fun() -> n) : unit -> 'a 
force x : 'a   <=> x() : 'a 

तो प्रकार 'a llist

type 'a llist = 'a cell Lazy.t 

यानी, किसी आलसी सेल मूल्य के बराबर है।

एक नक्शा कार्यान्वयन कि बंद में वापस ऊपर परिभाषा

let rec map f lst = 
    match force lst with 
    | Nil -> lazy Nil 
    | Cons (hd,tl) -> lazy (Cons (f hd, map f tl)) 

अनुवाद के संदर्भ में अधिक समझ बनाने सकता है:

let rec map f lst = 
    match lst() with 
    | Nil -> (fun() -> Nil) 
    | Cons (hd,tl) -> (fun() -> Cons (f hd, map f tl)) 

संलग्न साथ

इसी

let rec append a b = 
    match force a with 
    | Nil -> b 
    | Cons (hd,tl) -> lazy (Cons (hd, append tl b)) 

हो जाता है

let rec append a b = 
    match a() with 
    | Nil -> b 
    | Cons (hd,tl) -> (fun() -> Cons (hd, append tl b)) 

मैं आम तौर पर lazy वाक्यविन्यास का उपयोग करना पसंद करता हूं, क्योंकि इससे यह स्पष्ट हो जाता है कि क्या हो रहा है।

ध्यान दें, यह भी है कि एक आलसी निलंबन और एक बंद नहीं बिल्कुल बराबर हैं। उदाहरण के लिए,

let x = lazy (print_endline "foo") in 
    force x; 
    force x 

प्रिंट

foo 

जबकि

let x = fun() -> print_endline "foo" in 
    x(); 
    x() 

प्रिंट

foo 
foo 

अंतर यह है कि force अभिव्यक्ति के मूल्य की गणना करता है बिल्कुल एक बार।

Answer 3

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