قائمة لغة كامل الموضوعية: تنفيذ المهام إلحاقي وخريطة

Question

وأنا أحاول حاليا لتمديد برنامج لغة كامل الموضوعية صديق. انها مجموعة ضخمة من الوظائف اللازمة لبعض تحليل البيانات .. وبما أنني لست حقا الكراك لغة كامل الموضوعية أنا عالقة حاليا على (بالنسبة لي) تنفيذ قائمة غريب:

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

ولقد أحسب أن هذا هو تنفيذ نوعا من قائمة "كسول"، ولكن لا يوجد لدي اي فكرة كيف يعمل حقا. ولست بحاجة لتنفيذ إلحاق وظيفة خريطة القائم على نوع أعلاه. وقد حصلت على أي شخص فكرة كيف نفعل ذلك؟

وسيكون حقا أن يكون موضع تقدير أي مساعدة!

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

نعم، القوائم يمكن أن يكون لانهائي. سوف رمز المعطى في إجابات أخرى إلحاق إلى نهاية قائمة لا حصر لها، ولكن ليس هناك برنامج يمكنك إرسال مما يمكن مراقبة ما يتم إلحاق التالية قائمة لا نهائية.