Espressioni aritmetiche

Calcolo di espressioni aritmetiche

Un operatore è un modo conciso e leggibile per scrivere delle strutture. Da un punto di vista sintattico gli operatori, come '+','-','*','/' etc., giocano il ruolo di normali funtori, solo che possono essere scritti in maniera infissa (l'operatore viene scritto fra gli operandi). Così possiamo esprimere strutture con due notazioni equivalenti: a+b è la notazione infissa corrispondente alla struttura +(a,b) mentre a+b*c corrisponde alla struttura +(a,*(b,c)).
Si noti che agli operatori è associata una precedenza per cui la espressione a+b*c viene interpretata nel modo usauale, con il '*' che ha precedenza sul '+'.
Se scriviamo una espressione aritmetica come 3+2*(7-4) questa non viene calcolata ma è considerata dal Prolog come la struttura: +(3,*(2,-(7,4)))
Se scriviamo X = 3+2*(7-4) X viene istanziato alla struttura indicata X = +(3,*(2,-(7,4)))
Per calcolare una espressione bisogna usare il predicato is. Scrivendo X is 3+2*(7-4)allora l'espressione aritmetica viene effettivamente calcolata el il suo valore viene usato per istanziare X.
Possiamo anche scrivere qualcosa del tipo Y=7, Z=4, X is 3+2*(Y-Z) ma tutte le variabili che compaiono nell'espressione devono essere istanziate al momento del calcolo.

Contare gli elementi di una lista

Possiamo contare gli elementi di una lista utilizzando queste regole:

la lunghezza di una lista vuota è 0
la lunghezza di una lista L non vuota si ottiene sommando 1 alla lunghezza della sua coda.

In Prolog:

%file aritmetica/lung.pl
%
% calcola il numero di elementi
%che compongono una lista
%
lunghezza([],0).
lunghezza([_|Coda],N):-
  lunghezza(Coda,Ncoda),
  N is Ncoda + 1.

/*
?- lunghezza([a,b,c,d,e],N).
*/

Sommare gli elementi di una lista di numeri interi

Analogamente possiamo ottenere la somma degli elementi di una lista contenete numeri interi:

la somma degli elementi di una lista vuota vale 0
la somma degli elementi di una lista L non vuota si ottiene sommando il primo elemento alla somma degli elementi della sua coda.

Scrivi un predicato somma(L,N) che restituisca in N la somma degli elementi di L.

somma([],0).
somma([Testa|Coda],S):-
  somma(Coda,Scoda),
  S is Scoda + Testa.

Calcolare la media degli elementi di una lista di numeri interi sfruttando i predicati lunghezza e somma definiti in precedenza.

Operatori di confronto fra espressioni aritmetiche

Con gli operatori di confronto >,<,etc. possiamo confrontare espressioni aritmetche. Ad esempio il goal X < Y ha successo se X è stato istanziato ad un valore minore di quello di Y.

Esercizio: controllare se una lista contenente numeri interi è ordinata.

Ordinamento di una lista di numeri interi

Possiamo scrivere una procedura per odinare una lista di numeri interi in modo crescente con il così detto bubble sort, il cui algoritmo può essere espresso come segue. Per ordinare la lista L

trova nella lista L due elementi X e Y adiacenti con X > Y e scambiali. Sia L1 il risultato dello scambio, ordina ricorsivamente L1.
Se non ci sono elementi in L tali che X > Y allora la lista è ordinata.

Questo è il relativo programma Prolog:

% file: aritmetica/bubble.pl
%
% ordinamento di una lista di numeri interi
% con l'algoritmo di bubble sort.
%
% si puo' fare uno scambio 
ordina(L,Ordinata):-
  scambia(L,L1),
  !,
  ordina(L1,Ordinata).
% nessuno scambio e' possibile
% la lista e' ordinata
ordina(Ordinata,Ordinata).

% X e Y vanno scambiati
scambia([X,Y|Resto],[Y,X|Resto]):-
  X > Y.
% si cerca di fare uno scambio nella coda
scambia([X|Resto],[X|Resto1]) :-
  scambia(Resto,Resto1).
/* un goal
?- ordina([5,3,7,15,1,4],L).
*/

Notate che scambia fallisce se non è possibile effettuare nessuni scambio.

Esercizio: fusione (merge) di due liste. Supponiamo di avre due liste L1 e L2 ordinatate. Vogliamo ottenere una terza lista anch'essa ordinata che contenga gli elementi di L1 e di L2.