F# هياكل البيانات الوظيفية البحتة WeightBiasedLeftistHeap ex 3.4

Question

أنا أعمل على هياكل البيانات الوظيفية البحتة لأوكاساكي وأحاول إنشاء تطبيقات F# للأشياء.أقوم أيضًا بإجراء التمارين المذكورة في الكتاب (بعضها يمثل تحديًا كبيرًا).حسنًا، أنا عالق في التمرين 3.4 الذي يدعو إلى تعديل وظيفة الدمج الخاصة بـ WeightBiasedLeftistHeap بحيث يتم تنفيذها في تمريرة واحدة بدلاً من تنفيذ التمريرتين الأصليتين.

لم أتمكن من معرفة كيفية القيام بذلك بعد وكنت آمل في الحصول على بعض الاقتراحات.كان هناك آخر أضف هنا على SO حيث يقوم الرجل بذلك في SML عن طريق تضمين وظيفة makeT إلى حد كبير.لقد بدأت السير في هذا الطريق (في القسم الذي تم التعليق عليه 3.4 المحاولة الأولى.لكني تخليت عن هذا النهج لأنني اعتقدت أن هذا لم يتم تنفيذه في تمريرة واحدة (يظل مستمرًا حتى الوصول إلى ورقة ثم يتم فكه وإعادة بناء الشجرة).هل أنا مخطئ في تفسير ذلك على أنه لا يزال عبارة عن دمج تمريرتين؟

فيما يلي رابط لتطبيقي الكامل لـ WeightBiasedLeftistHeap.

فيما يلي محاولاتي الفاشلة للقيام بذلك في F#:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB + 1, x, b, a)

    // excercise 3.4 first try
    //    let rec merge3_4 l r =
    //        match l,r with
    //        | l,E -> l
    //        | E,r -> r
    //        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
    //            if lx <= rx then
    //                let right = merge3_4 lb rh
    //                let weightA = weight la
    //                let weightB = weight right
    //
    //                if weightA >= weightB then
    //                    T(weightA + weightB + 1, lx, la, right)
    //                else
    //                    T(weightA + weightB + 1, lx, right, la)
    //            else
    //                let right = merge3_4 lh rb
    //                let weightA = weight ra
    //                let weightB = weight right
    //
    //                if weightA >= weightB then 
    //                    T(weightA + weightB + 1, rx, ra, right)
    //                else
    //                    T(weightA + weightB + 1, rx, right, ra)

    // excercise 3.4 second try (fail!)
    // this doesn't work, I couldn't figure out how to do this in a single pass
    let merge3_4 l r =
        let rec merge' l r value leftChild  =
            match l,r with
            | l,E -> makeT value leftChild l
            | E,r -> makeT value leftChild r
            | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
                if lx <= rx then
                    merge' lb rh lx la   //(fun h -> makeT(lx, la, h))
                else
                    merge' lh rb rx ra   //(fun h -> makeT(rx, ra, h))

        match l, r with
        | l, E -> l
        | E, r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            let lf = fun h -> makeT(lx, la, h)
            if lx <= rx then
                merge' lb rh lx la // (fun h -> makeT(lx, la, h))
            else
                merge' lh rb rx ra // (fun h -> makeT(rx, ra, h))

    let rec merge l r =
        match l,r with
        | l,E -> l
        | E,r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            if lx <= rx then
                makeT lx la (merge lb rh)
            else
                makeT rx ra (merge lh rb)

    let insert3_4 x h =
        merge3_4 (T(1,x,E,E)) h

Answer 1

السؤال الأول هو:ما الذي يشكل خوارزمية "المرور الواحد"؟الشيء الذي يمكن تنفيذه بشكل طبيعي كحلقة واحدة من أعلى إلى أسفل سيكون مؤهلاً.على النقيض من ذلك، فإن التكرار - الذي تم تجميعه بسذاجة - عادةً ما يكون له مروران، أحدهما في الطريق إلى الأسفل والآخر في طريق العودة إلى الأعلى. العودية الذيل يمكن تجميعها بسهولة في حلقة، وعادةً ما تكون باللغات الوظيفية. سلبيات وحدة العودية الذيل هو تحسين مشابه، وإن كان أقل شيوعًا.ولكن، حتى لو كان المترجم الخاص بك لا يدعم سلبيات وحدات التكرار، يمكنك بسهولة تحويل مثل هذا التنفيذ إلى حلقة يدويًا.

تشبه سلبيات معامل العودية الذيل العودية العادية، فيما عدا أن الاستدعاء الخلفي مغلف في مُنشئ، والذي يمكن تخصيصه وملؤه جزئيًا قبل الاستدعاء العودي.في هذه الحالة، قد ترغب في أن تكون تعبيرات الإرجاع شيئًا مثل T (1+size(a)+size(b)+size(c),x,a,merge(b,c)).الرؤية الأساسية المطلوبة هنا (كما هو مذكور في التعديل على ملف موضوع SO آخر) هو أنك لا تحتاج إلى إجراء الدمج لمعرفة حجم النتيجة، وبالتالي أي جانب من الشجرة الجديدة يجب أن يستمر.وذلك لأن حجم merge(b,c) سوف يكون دائما size(b)+size(c), ، والتي يمكن حسابها خارج الدمج.

لاحظ أن الأصل rank وظيفة لأكوام اليسار العادي لا لا مشاركة هذه الخاصية، وبالتالي لا يمكن تحسينها بهذه الطريقة.

بشكل أساسي، تقوم بتضمين المكالمتين لإجراء T و أيضا تحويل مكالمات النموذج size(merge(b,c)) ل size(b)+size(c).

بمجرد إجراء هذا التغيير، تصبح الوظيفة الناتجة أكثر كسلاً بكثير من الوظيفة الأصلية، لأنها يمكنها إرجاع جذر النتيجة قبل تقييم الدمج العودي.

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

Answer 2

لست متأكدًا تمامًا مما إذا كنت قد فهمت السؤال بشكل صحيح، ولكن هذه هي محاولتي - حاليًا، merge تقوم العملية بإجراء مكالمة متكررة إلى merge (هذا هو التمرير الأول) وعندما يصل إلى نهاية الكومة (أول حالتين في match)، يقوم بإرجاع الكومة التي تم إنشاؤها حديثًا إلى المتصل والمكالمات makeT عدة مرات (وهذا هو التمريرة الثانية).

لا أعتقد أن ذلك مجرد تضمين mMakeT هو ما يُطلب منا القيام به (إذا كانت الإجابة بنعم، فما عليك سوى إضافة inline ل makeT ويتم ذلك دون جعل التعليمات البرمجية أقل قابلية للقراءة :-)).

لكن ما يمكن فعله هو تعديل merge دالة لاستخدام نمط التمرير المستمر حيث يتم تمرير "بقية العمل" كدالة إلى الاستدعاء العودي (لذلك لا يوجد عمل معلق على المكدس يجب القيام به بعد اكتمال المرور الأول).يمكن القيام بذلك على النحو التالي:

let rec merge' l r cont =
    match l,r with
    | l,E -> cont l // Return result by calling  the continuation
    | E,r -> cont r // (same here)
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
        if lx <= rx then
            // Perform recursive call and give it 'makeT' as a continuation
            merge' lb rh (makeT lx la)
        else
            // (same here)
            merge' lh rb (makeT rx ra)

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed
let merge l r = merge' l r id

لست مقتنعًا تمامًا بأن هذه هي الإجابة الصحيحة - فهي تؤدي تمريرة واحدة فقط، ولكن العمل المجمع (في المتابعة) يعني أن التمريرة أطول بمرتين.ومع ذلك، لا أرى طريقة لتبسيط الأمر، لذا قد تكون الإجابة الصحيحة...