Elaborazione di un albero in F # usando le continuazioni

Question

Sto cercando di capire come funzionano le continuazioni, ho questo esempio che ho trovato nel libro, Programmazione funzionale del mondo reale di Tomas Petricek con Jon Skeet. Ma questo in realtà ha ottenuto la mia testa gira quindi devo chiedere qualche aiuto dettagliata ..

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))) 

Ok ecco quello che sono stato in grado di capire me stesso ... Nel secondo ramo abbiamo prima di elaborare il lato sinistro il nodo e passare un lambda. Questo lambda creerà un'istanza di una classe di chiusura con due campi, right: IntTree e cont: (int -> 'a) che verrà invocato dal caso base. Ma poi sembra anche che il "inner lambda" catturi lo leftSum ma non capisco bene come tutto si combini, devo ammettere che mi viene un po 'di vertigini quando cerco di capirlo.

Answer 1

Penso che la risposta di Christian sia buona: lo stile di passaggio di continuazione è in realtà solo una (non così) semplice trasformazione meccanica eseguita sul codice sorgente originale. Questo potrebbe essere più facile da vedere quando si fa un passo alla volta:

1) Iniziare con il codice originale (qui, a cambiare il codice per fare solo un'operazione per riga):

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

2) Aggiungi il parametro di continuazione e chiamalo invece di restituire il risultato (questo non è ancora ricorsivo in coda). Per fare questo tipo di controllo, ho aggiunto continuazione fun x -> x ad entrambi i sub-chiamate in modo che appena ritornano la somma come risultato:

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) Ora, cambiamo la prima chiamata ricorsiva ad utilizzare continuazione stile di passaggio - sollevare il resto del corpo nel seguito:

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) e ripetere la stessa cosa per la seconda chiamata ricorsiva:

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

Potrebbe essere più facile da Grok se si considera prima questa espressione per calcolare la somma di un albero:

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

Il problema di questa soluzione è che trabocca stack per alberi di grandi dimensioni a causa di un eccessivo stack frame allocazioni. La soluzione è utilizzare assicurarsi che la chiamata ricorsiva sia in posizione di coda, il che significa che non è possibile eseguire alcuna operazione dopo la chiamata (nel caso precedente, l'aggiunta viene eseguita dopo le chiamate ricorsive). In questo caso il compilatore può eliminare i frame di stack non necessari e quindi evitare l'overflow. La tecnica per risolvere questo è usare lo stile di passaggio continuo come nella soluzione di Tomas e Jon. Come puoi vedere, le continuazioni qui usate assicurano che nessuna operazione venga eseguita dopo le chiamate ricorsive.

Answer 3

feci una dra Visio Ala nel processo di cercare di capire questo, ho pensato che potrei condividerlo qui nel caso in cui aiuti qualcun altro. Mi rendo conto che potrebbe finire per essere più confuso per alcuni, ma per gli studenti visivi (come me) mi sembra che abbia reso più chiaro il disegno di un esempio di come potrebbe sembrare di elaborare un albero come questo.