Una tabella di traccia è una tecnica utilizzata per testare gli algoritmi.
"The table usually takes the form of a multi-column, multi-row table; With each column showing a variable, and each row showing each number input into the algorithm and the subsequent values of the variables." ~ Wikipedia
Mentre in un linguaggio puramente funzionale le variabili non cambiano i loro valori, questa tecnica ha qualche utilità?
È meno utile in un linguaggio puramente funzionale (o anche quando si programma in puro stile in un linguaggio altrimenti impuro). Tuttavia, puoi ancora utilizzarlo interpretandolo in modo leggermente diverso: ad es. in una funzione ricorsiva, il binding del parametro non può cambiare il suo valore nella funzione, ma per ogni chiamata ricorsiva, il parametro same sarà associato a un diverso valore, quindi se reinterpretate le chiamate ricorsive come una sequenza , il parametro ancora appare per cambiare l'associazione nel tempo (anche se in realtà è un diverso associazione in un ambito dinamico diverso (frame dello stack)).
Tutti gli esempi di tabelle di traccia che sono stato in grado di trovare durante una ricerca rapida implicano il looping e la ricorsione in coda è essenzialmente il modo puro di fare il ciclo. Prendi l'esempio fattoriale "canonico", ricorsivo alla coda:
factorial n = fact' n 1
where
fact' 0 acc = acc
fact' n acc = fact' (n-1) (n*acc)
Puoi facilmente creare una tabella di traccia per la funzione helper ricorsiva di coda fact' , prendiamo il fattoriale di 4:
n acc
--------
4 1
3 4
2 12
1 24
0 24
--------
ret: 24
Tecnicamente parlando, n e acc non cambiano, piuttosto ci sono 5 diversi n se acc s. Ma puoi ancora pensarlo in questo modo.
Tuttavia, pensare al flusso di dati è spesso più utile del pensare a cambiamenti di stato nella pura programmazione funzionale. E pensare a concetti di più alto livello, più astratti come mappe, pieghe, scansioni, monoidi, monadi, funtori, frecce, semigruppi, ecc. factorial può essere banalmente espresso come fold :
factorial 0 = 1
factorial n = foldl1 (*) [1..n]
Leggi altre domande sui tag testing functional-programming algorithms