Post on 01-May-2015
L’APPROCCIO FUNZIONALE
Obiettivo: esprimere la soluzione di un problema sotto forma di funzione.
• Quali funzioni primitive?
• Quali meccanismi di combinazione?
UN POSSIBILE INSIEME DI PRIMITIVE
La funzione zero: zero: NN La funzione successore: succ: NN una famiglia di funzioni proiezione:
pni: NnN (1 i n)
la funzione pni seleziona l’i-esimo para-metro fra gli n parametri di ingresso
p3,2(x1, x2, x3) = x2
MECCANISMI DI COMBINAZIONE
Partendo da
• le funzioni primitive sui naturali• l’operatore di uguaglianza• le espressioni condizionali• la ricorsione
è possibile definire alcune funzioni chesiamo abituati da sempre a considerare date a priori.
FUNZIONI ELEMENTARI
In questi esempi:
• non avremo bisogno delle funzioni di proiezione pni, perché possediamo la capacità espressiva di denotare ogni singolo parametro nel corpo della funzione per nome
• denoteremo con 0 il valore restituito dalla funzione zero.
PREDECESSORE
Precedessore in termini del successore:
y = pred(x) x = succ(y)
int pred(int x){ return (x==1) ? 0 : raggiungi(x,0); }
int raggiungi(int x, int y){ return (x==succ(y)) ? y :
raggiungi(x,succ(y)); }
PREDECESSORE: FUNZIONAMENTO
Cliente Chiama(main) Pred(3)Pred(3) raggiungi(3,0)raggiungi(3,0) raggiungi(3,1)raggiungi(3,1) raggiungi(3,2)raggiungi(3,2) 2
SOMMA
Somma in termini di successore e precedessore :
x + y = 1+((x-1)+y)
int sum(int x, int y){ return (x==0) ? y :
succ(sum(pred(x),y)); }
SOMMA: FUNZIONAMENTO
Cliente Chiama(main) sum(3,5)sum(3,5) succ(sum(2,5))sum(2,5) succ(sum(1,5))sum(1,5) succ(sum(0,5))sum(0,5) 5
succ(5) 6succ(6) 7succ(7) 8
MOLTIPLICAZIONE
Prodotto in termini di precedessore e somma:
x * y = y + (x-1)*y
int mul(int x, int y){ return (x==0) ? 0 :
sum(mul(pred(x),y),y); }
MOLTIPLICAZIONE: FUNZIONAMENTO
Cliente Chiama(main) mul(3,6)mul(3,6) sum(mul(2,6),6)mul(2,6) sum(mul(1,6),6)mul(1,6) sum(mul(0,6),6)mul(0,6) 0
sum(0,6) 6sum(6,6) 12sum(12,6) 18
SOTTRAZIONE
Differenza in termini del precedessore :
x - y = (x-(y-1))-1
int diff(int x, int y){ return (y==0) ? x :
pred(diff(x,pred(y))); }
SOTTRAZIONE: FUNZIONAMENTO
Cliente Chiama(main) diff(2,3)diff(2,3) pred(diff(2,2))diff(2,2) pred(diff(2,1))diff(2,1) pred(diff(2,0))diff(2,0) 2
pred(2) 1pred(1) 0pred(0) -1
OPERATORI RELAZIONALI
int maggioreDiZero(int x){ return (x==0) ? 0 : succ(0);}
int minoreDiZero(int x, int y){ return maggioreDiZero(diff(y,x));}
OPERATORI LOGICI
int and(int p, int q){return p ? q : 0;
}
int or(int p, int q){return p ? p : q;
}
ALCUNI ESERCIZI
Obiettivo: esprimere la soluzione di alcuni problemi per via funzionale,sfruttando la ricorsione.
• Calcolo della funzione H(n) = 1 + 1/2 + 1/3 + … + 1/n
• Calcolo della potenza n-esimabk con bZ, k0
PROBLEMA 1: H(n)
• H: N R (int double)
H(n) = 1 + 1/2 +1/3 + ... + 1/n
• Per n>1 la funzione si riscrive come:
H(n) = (1 + 1/2 +1/3 + ... + 1/(n-1)) + 1/n
ossia come
H(n) = H(n-1) + 1/n
mentre, ovviamente, H(1)=1.
PROBLEMA 1: H(n)
• Dunque,
H(n) = 1 per n=1
H(n) = 1/n + H(n-1) per n>1• da cui:double H(int n){
return (n==1) ? 1 : 1.0/n + H(n-1);
}
PROBLEMA 2: bk con bZ, k0
• power: RN R (doubleint double)
bk = 1 per k=0
bk = b * bk-1 per k>0
• da cui:double power(double b, int k){
return (k==0) ? 1 : b*power(b,k-1);
}
ALTRI ESERCIZI
Obiettivo: esprimere la soluzione di alcuni problemi per via funzionale,sfruttando la ricorsione.
• Calcolo del valore di un polinomio di grado n a coefficienti unitari
P(x,n) = x0 + x1 + … xn
• Fattoriale “innovativo”
PROBLEMA 3: POLINOMIO
• Calcolo del valore di un polinomio di grado n0 a coefficienti unitari
P(x,n) = x0 + x1 + … xn
• Per n>0 P(x,n) si riscrive come:
P(x,n) = (x0 + x1 + … xn-1) + xn
ossia come
P(x,n) = P(x,n-1) + xn
mentre, ovviamente, P(x,0)=1.
PROBLEMA 3: POLINOMIO
• Dunque,
pol(x,n) = 1 per n=0
pol(x,n) = xn + pol(x,n-1) per n>0• da cui:double pol(double x, int n){
return (n==0) ? 1 : power(x,n) + pol(x,n-1);
}
UN DIVERSO APPROCCIO
• Raccogliendo x a fattore comune, il polinomio si può riscrivere come:P(x,n) = 1 + x1 + … xn =
= 1+ x * (1 + x1 + x2 + … xn-1) == 1+ x * (1 + x * (1 + x + … xn-2)) =...= 1+ x *(1+ x * (…( 1+(x+1)*x)…))
UN DIVERSO APPROCCIO
• Questo suggerisce un diverso modo di procedere:P(x,n) =
= 1+ x *(1+ x * (…( 1+(x+1)*x)…))
• Detto v il valore tra parentesi:P(x,0) = v0 = 1
P(x,n) = vn = 1 + x * vn-1
v
UN DIVERSO APPROCCIO - ESEMPIO
x4 + x3 + x2 + x1 + x0=(( ( x + 1 ) *x + 1 ) * x +1) *x
+1v0 = 1
v1 = v0*x + 1
v2 = v1*x + 1
v3 = v2*x + 1
v4 = v3*x + 1
0
1
2
3
4
UN DIVERSO APPROCCIO
• La relazione:P(x,0) = v0 = 1 P(x,n) = vn = 1 + x * vn-1
• può essere interpretata dicendo:– al passo k=0, il valore del polinomio è 1– al passo k, il valore corrente del
polinomio è 1+x*v (v = valore del polinomio al passo k-1)
– il valore v dopo il passo k=n dà il valore finale del polinomio.
UN DIVERSO APPROCCIO
• Nuova codifica con due funzioni:
– una funzione pol(), inalterata rispetto a prima, per mascherare la differenza agli occhi del cliente
– una funzione polin() come servitore privato di pol(), che opera secondo il nuovo principio di “accumulo”.
UN DIVERSO APPROCCIO
• Al passo k il valore del polinomio è 1+x*v• il valore v dopo il passo k=n dà il valore
finale di P(x,n)
double polin(double x, int n,double v, int k)
{
return (k==n) ? v :
polin(x,n,1+x*v,k+1);}
UN DIVERSO APPROCCIO
• Al passo k il valore del polinomio è 1+x*v• il valore v dopo il passo k=n dà il valore
finale di P(x,n)
double polin(double x, int n,double v, int k)
{
return (k==n) ? v :
polin(x,n,1+x*v,k+1);}
v rappresenta vk, cioè il valore del polinomio quando il passo k-esimo
è già stato svolto
Quindi, il valore finale desiderato vn è il valore di v quando k=n.
UN DIVERSO APPROCCIO
double pol(double x, int n){
return polin(x,n,1,0);
}
double polin(double x, int n,double v, int k){
return (k==n) ? v :polin(x,n,1+x*v,k+1);
}
situazione iniziale: vk=0 = 1
UN FATTORIALE… INNOVATIVO!
• Definizione:
n! = 1 * 2 * 3 *… * n
• Detto vn = 1 * 2 * 3 *… * n, si può scrivere:
1! = v1 = 1
n! = vn = vn-1 * n
UN FATTORIALE… INNOVATIVO!
• La relazione:1! = v1 = 1 n! = vn = n * vn-1
• può essere interpretata dicendo:– al passo k=1, il valore del fattoriale è 1– al passo k, il valore del fattoriale è k*v
(v = valore del fattoriale al passo k-1)– il valore v dopo il passo k=n dà il valore
finale del fattoriale.
UN FATTORIALE… INNOVATIVO!
• Nuova codifica con due funzioni:
– una funzione fact(), inalterata rispetto a prima, per mascherare la differenza agli occhi del cliente
– una funzione factIter() come servitore privato di fact(), che opera secondo il nuovo principio di “accumulo”.
UN FATTORIALE… INNOVATIVO!
int fact(int n){
return factIter(n,1,1);
}
int factIter(int n, int v, int k){
return (k==n) ? v :factIter(n, (k+1)*v,
k+1);
}
UN FATTORIALE… INNOVATIVO!
int fact(int n){
return factIter(n,1,1);
}
int factIter(int n, int v, int k){
return (k==n) ? v :factIter(n, (k+1)*v,
k+1);
}
Situazione iniziale: vk=1 = 1
UN FATTORIALE… INNOVATIVO!
int fact(int n){
return factIter(n,1,1);
}
int factIter(int n, int v, int k){
return (k==n) ? v :factIter(n, (k+1)*v,
k+1);
}
v rappresenta il valore delfattoriale dopo il passo k-esimo
Quindi, il valore dopo il passo n è disponibile quando k=n.
UN FATTORIALE… INNOVATIVO?
Perché questo esempio è “innovativo” ?
il risultato viene sintetizzato via via che le chiamate si aprono, “in avanti”.
È una soluzione sintatticamente ricorsiva..
… ma che dà luogo a un un processo computazionale iterativo.
infatti, dopo k passi, abbiamo a disposizione il risultato parziale relativo a fact(k)
UN FATTORIALE… INNOVATIVO?
Perché questo esempio è “innovativo” ?
il risultato viene sintetizzato via via che le chiamate si aprono, “in avanti”.
È una soluzione sintatticamente ricorsiva..
… ma che dà luogo a un un processo computazionale iterativo.
infatti, dopo k passi, abbiamo a disposizione il risultato parziale relativo a fact(k)
È un caso di RICORSIONE TAIL