Come farei per rendere questa coda ricorsiva?

Question

Ho questo codice:

(define (prog1 x y) 
    (let ([rel (related x y)]) 
     (cond 
     [(null? rel) (list x)] 
     [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))]))) 

Quello che voglio fare è cercare di renderlo ricorsiva in coda. So che ho bisogno di fare qualcosa di simile:

(define (prog1 x y) 
    (prog1-iter x y `())) 

(define (prog1-iter x y acc) 
    (... 
    )) 

Ma non sono sicuro come andare dal mio codice a questo codice ... Penso che sia perché l'originale ha una mappa in esso e sono sicuri di come incorporalo in un . Qualcuno potrebbe indicarmi la direzione giusta!

Answer 1

La ricorsione in coda è facile da scrivere per cose che sono intrinsecamente iterative. La tua funzione si chiama potenzialmente molte volte, quindi non sarà semplice. Ciononostante, qualsiasi programma può essere reso iterativo (ad esempio, il tuo computer è una macchina iterativa gigante), quindi può essere fatto.

Prima di tutto, la vostra funzione non è direttamente ricorsiva (cioè prog1 non chiama direttamente in sé). Piuttosto, prog1 chiama map, che quindi chiama il lambda che gli hai dato (forse più volte), che quindi chiama prog1; quindi è indiretto La chiamata a map non è una coda; la chiamata da map a lambda non è certo una coda (potrebbe essere necessario chiamarla più di una volta); e la chiamata da lambda a prog1 è una coda.

Pertanto, non sono sicuro di cosa esattamente richiedi quando chiedi che sia "coda-ricorsiva". Vuoi che ogni chiamata nella catena di chiamate da prog1 diventi una chiamata di coda? O vuoi rendere ogni chiamata nel programma una coda? Esistono "coda-recursive" versioni di map, ma sono solo "ricorsiva in coda rispetto alle chiamate da map a map, e non chiamate alla funzione di mappatura, in modo che non sono utili per il vostro caso.

Il il metodo generale per chiamare ogni chiamata in un programma è chiamato continuation-passing style. Fondamentalmente, ogni funzione accetta un argomento di funzione aggiuntivo, la "continuazione". Invece di fare una chiamata non-tail a una funzione, si effettua una chiamata tail a esso e passa una continuazione specificando come elaborare i risultati della chiamata di funzione. Fondamentalmente, la continuazione comprenderebbe il "resto della" funzione originale dopo la chiamata non-tail, e richiederebbe il "risultato di ritorno" di l'originale non-tail call come argomento. Lascerò come esercizio come convertire y il nostro programma a CPS.