kullanarak F # bir ağaç işleme continuations

Question

, ben kitabın Jon Skeet ile Tomas Petriček tarafından Gerçek Dünya Fonksiyonel Programlama rastladı bu örneği var. Ama burada

type IntTree = 
    | Leaf of int 
    | Node of IntTree * IntTree 

let rec sumTreeCont tree cont = 
    match tree with 
    | Leaf(n) -> cont(n) 
    | Node(left, right) -> 
     sumTreeCont left (fun leftSum -> 
     sumTreeCont right (fun rightSum -> 
      cont(leftSum + rightSum))) 

Tamam bazı ayrıntılı yardım istemek gerekir böylece iplik bu gerçekten var başım .. ben ... Kendimi anlamaya mümkün olmuştur İkinci dallanma öncelikle sol tarafını işlemek ne Düğüm ve bir lambda geçirin. Bu lambda, taban alanı tarafından çağrılacak olan iki alanla, right: IntTree ve cont: (int -> 'a) ile bir kapatma sınıfı oluşturacaktır. Ama o zaman "iç lambda" leftSum'u yakalar ama bütün bunların nasıl bir araya geldiğini tam olarak anlayamıyorum, bunu anlamaya çalıştığımda biraz başım dönüyor olduğumu itiraf etmeliyim.

Answer 1

Christian'ın cevabının iyi olduğunu düşünüyorum - devam eden geçiş stili gerçekten orijinal kaynak kodunda yaptığınız basit bir mekanik dönüşümdür.

1 tek satır başına bir operasyon yapmak, I) kodunu değiştirmek burada (orijinal kod ile başlayın): Bu adım adım ne zaman görmeye daha kolay olabilir

let rec sumTree tree = 
    match tree with 
    | Leaf(n) -> n 
    | Node(left, right) -> 
     let leftSum = sumTree left 
     let rightSum = sumTree right 
     leftSum + rightSum 

2) Devam parametresi ekleyin ve sonucu döndürmek yerine onu arayın (bu hala kuyruk özlemi değil). onlar sadece sonucu toplamını döndürür, böylece bu tip çek yapmak için, ben alt aramalar hem devamını fun x -> x eklendi:

let rec sumTree tree cont = 
    match tree with 
    | Leaf(n) -> cont n 
    | Node(left, right) -> 
     let leftSum = sumTree left (fun x -> x) 
     let rightSum = sumTree right (fun x -> x) 
     cont (leftSum + rightSum) 

3) Şimdi, devam geçen tarzını kullanan ilk özyinelemeli çağrı değiştirelim - devamında içine vücudun geri kalanını kaldırmak:

let rec sumTree tree cont = 
    match tree with 
    | Leaf(n) -> cont n 
    | Node(left, right) -> 
     sumTree left (fun leftSum -> 
     let rightSum = sumTree right (fun x -> x) 
     cont (leftSum + rightSum)) 

4) ikinci özyinelemeli arama için aynı şeyi tekrarlamak:

let rec sumTree tree cont = 
    match tree with 
    | Leaf(n) -> cont n 
    | Node(left, right) -> 
     sumTree left (fun leftSum -> 
     sumTree right (fun rightSum -> 
      cont (leftSum + rightSum))) 

Answer 2

öncelikle bir ağaç toplamını hesaplamak için bu ifade düşünün grok daha kolay olabilir

:

let rec sumTree tree = 
    match tree with 
    | Leaf(n) -> n 
    | Node(left, right) -> 
     sumTree left + sumTree right 

bu çözümdeki sorun aşırı yığın çerçevesi nedeniyle büyük ağaçlar için yığın taşmakta olan tahsisler. Çözüm, tekrarlamalı aramanın kuyruk pozisyonunda olduğundan emin olun, yani aramadan sonra herhangi bir işlemi yapamayacağınız anlamına gelir (yukarıdaki durumda, tekrar eden aramalardan sonra ekleme yapılır). Bu durumda, derleyici gereksiz yığın çerçevelerini ortadan kaldırabilir ve dolayısıyla taşmayı önleyebilir. Bunu çözme tekniği, Tomas ve Jon'un çözümlerinde olduğu gibi devam eden geçiş stilini kullanmaktır. Gördüğünüz gibi, burada kullanılan süreksizlikler, özyinelemeli aramalardan sonra hiçbir işlem yapılmadığından emin olurlar.

Answer 3

bir Visio dra yapılan Bunu anlamaya çalışırken, bir başkasına yardım etmesi durumunda burada paylaşabileceğimi düşündüm. Bazıları için biraz daha kafa karıştırıcı olabileceğinin farkına vardım ama görsel öğrenenler için (benim gibi), böyle bir ağacın nasıl işlenebileceğine dair bir örnek çizerek, işleri daha net hale getirmiş gibi hissediyorum.