({{}})

({{, ({{"Lezione 9"}, {"L'approccio funzionale e il pattern matching"}, {Crescenzio Gallo - Università di Foggia
crescenzio.gallo@unifg.it}})}})

Note:

Il materiale visualizzato durante questo seminario è disponibile per il download all'indirizzo http://www.crescenziogallo.it/unifg/seminario-mathematica-2014/

Per una migliore visione ingrandire lo schermo mediante il pulsante in alto a destra "Schermo intero"

11-25 Marzo 2014

Agenda

Introduzione

Mathematica è un linguaggio

Mathematica è un linguaggio funzionale e simbolico

Le basi della logica funzionale

L’approccio funzionale

Il pattern e il pattern matching

Le funzioni pure

Ragionare per funzioni

Gli script one-line

Conclusioni

Introduzione: Mathematica è un linguaggio

Poichè siamo abituati ad usare Mathematica attraverso il front-end, capita spesso di pensare di non considerare la vera natura di Mathematica ossia quella di linguaggio di programmazione.
Già nel fare un semplice calcolo e renderlo parametrico e farlo computare al variare del parametro in effetti abbiamo sfruttato la capacità di programmazione del linguaggio Mathematica:

Expand[((((((z+1))^2)+1))^2)]

Manipulate[Expand[((((((z+1))^2)+1))^n)],{n,2,10,1}]

Introduzione: Mathematica è un linguaggio funzionale e simbolico

Il principio di base di Mathematica è “Everything is an expression”.

Ad eccezione delle entità atomiche (numeri, stringhe, simboli), tutto viene convertito internamente in espressioni o nidificazioni di espressioni.

La manipolazione delle espressioni permette a Mathematica di eseguire calcoli simbolici, di modificare interattivamente grafici o strutture dati, di animare o consentire all'utente di manipolare oggetti attraverso semplici interfacce.
Vediamo come viene rappresentato internamente un numero razionale:

FullForm[(1/3)]

TreeForm[(1/3)]

Un binomio:

FullForm[a+b x]

TreeForm[a+b x]

Un grafico:

gr=Graphics[{Blue, Circle[{0,0}]}]

FullForm[gr]

TreeForm[gr]

Introduzione: Mathematica è un linguaggio funzionale e simbolico

In Mathematica ogni oggetto è un’espressione che può essere gestita tramite le funzioni: implicazioni pratiche.

Qualsiasi espressione può essere inclusa in qualsiasi altra espressione.

Esempio 1

Manipolare l’espressione di un grafico dopo averlo realizzato, ad esempio per ribaltare l’asse delle x rispetto a quello delle y:

Plot[Cos[x]+x,{x,0,10}]

s=FullGraphics[Plot[Cos[x]+x,{x,0,10}]]

ReplaceAll[s,{x_Real,y_Real}->{-x,y}]

Esempio 2

Possiamo eseguire operazioni su liste di oggetti di qualsiasi natura. Ad esempio, contare le ricorrenze di ciascun elemento grafico in una lista di 20 elementi:

spheres=RandomChoice[{,,},20]

Tally[spheres]

Il concetto di espressione diviene fondamentale in relazione alla logica funzionale del linguaggio Mathematica perchè - per poter sfruttare al meglio le funzioni da applicare sui dati - bisogna considerare in maniera corretta i dati, ossia vederli sempre come espressioni ancor prima di essere liste, array, matrici, polinomi o qualsiasi altra cosa.

Le basi della logica funzionale: l’approccio funzionale

Vediamo un semplice esempio di come un algoritmo può essere riscritto secondo diversi stili di programmazione.

Esempio 3: la distanza tra un punto nel piano e l’origine degli assi.

Dato un array di coppie che rappresentano punti nel piano, dobbiamo calcolare l’array delle distanze di ciascun punto dall’origine degli assi:

punti=RandomInteger[{-5,5},{10,2}]

Nell’approccio procedurale definisco un ciclo che prende ciascun elemento della lista e ne calcola la distanza dall’origine degli assi:

DistanzaP[lista_]:=
Module[{risultato},
risultato=Table[Null,{Length[lista]}];
Do[
risultato[[i]]=(Sqrt[((lista[[i,1]])^2)+((lista[[i,2]])^2)]),
{i,1,Length[lista]}
];
Return[risultato]]

DistanzaP[punti]

Nell’approccio funzionale applico una funzione all’intero data set, senza dover gestire io manualmente lo scorrimento degli elementi nel data set stesso:

DistanzaF[lista_]:=Map[Norm,lista]

DistanzaP[punti]

Vediamo la differenza di tempo

punti=RandomInteger[{-5,5},{10000,2}];

AbsoluteTiming[a=DistanzaP[punti];]

AbsoluteTiming[b=DistanzaF[punti];]

Confrontiamo anche che i risultati siano uguali:

a==b

Si potrebbe osservare che nella funzione DistanzaF si è usata la funzione Norm al posto del calcolo della radice. In effetti, nell’approccio procedurale in genere si è portati più a costruire la soluzione passo per passo a partire dai dati disponibli e con le formule della teoria; mentre, con una forma mentis più rivolta alle funzioni ed all’approccio funzionale, si ha una maggiore propensione a cercare sempre una funzione che implementa la formula necessaria e poi applicare tale funzione al data set in questione.
Comunque, anche eliminando la semplicità della funzione Norm, si ha un vantaggio di tempo:

DistanzaF1[lista_]:=Map[(Sqrt[Apply[Plus,((#)^2)]])&,lista]

Si noti come in una logica funzionale si è usato il valore dell’attributo Listable della funzione Power e l’Apply per costruire la somma degli elementi di un array, cose che nella logica procedurale non esistono e dunque non si sono usati:

AbsoluteTiming[c=DistanzaF1[punti];]

a===b===c

In ogni caso, anche operando al contrario (ossia usando Norm dentro l’algoritmo procedurale) non si ottiene alcun miglioramento:

DistanzaP1[lista_]:=
Module[{risultato},
risultato=Table[Null,{Length[lista]}];
Do[
risultato[[i]]=Norm[lista[[i]]],
{i,1,Length[lista]}
];
Return[risultato]]

AbsoluteTiming[d=DistanzaP1[punti];]

d===c

Vediamo un altro possible approccio, anche questo molto vicino alla natura di Mathematica: ossia l’approccio “Rule-Based”, che utilizza le regole di sostituzione al posto delle funzioni per operare sui dati:

DistanzaRB[lista_]:=lista/.{x_,y_}:>Norm[{x,y}]

AbsoluteTiming[e=DistanzaRB[punti];]

e===c

?ReplaceAll

punti[[1;;20]]

punti[[1;;20]]/.{x_,y_}:>Norm[{x,y}]

Le basi della logica funzionale: il pattern e il pattern matching

Se devo applicare una funzione ad un intero elenco di oggetti posso facilmente procedere anche senza ricorre ai pattern, nel senso che indistintamente applico la funzione all’intera lista di oggetti. In realtà, in molti casi non ci troviamo in situazioni così semplici; per cui, dato un insieme di valori, dobbiamo filtrare quelli a cui siamo interessati perchè solo a quelli dobbiamo applicare una certa funzione. In questo caso interviene il concetto di pattern e la tecnica del pattern matching.

Esempio 4: Miglioriamo la funzione Distanza

Nell’esempio di sopra, a prescindere da quale versione consideriamo, ci sono diversi punti deboli della soluzione costruita. Vediamo qualche esempio.

DistanzaF[{{2,-3},{4,-1},{2,1},{9,3,2}}]

DistanzaRB[{{2,-3},{4,-1},{2,1},{9,3,2}}]

DistanzaF1[{{2,-3},{4,-1},{2,1},{9,3,2}}]

DistanzaP[{{2,-3},{4,-1},{2,1},{9,3,2}}]

Vediamo che solo alcuni hanno risposto correttamente, ossia DistanzaF e DistanzaF1 perchè sono basati su funzioni che non dipendono dalla struttura della lista, se a due o tre dimensioni.
Se vogliamo rendere queste funzioni più corrette e farci restituire un valore diverso a seconda dei diversi casi, possiamo ad esempio introdurre dei pattern per la variabile di input lista in modo che, a seconda dei casi, possiamo eseguire un calcolo diverso. Scegliamo una sola delle funzioni sopra usate:

Distanza[lista_]:=Map[Norm,lista]

Se vogliamo farla funzionare solo nel caso di elementi di tipo coppie, possiamo usare il seguente filtro:

Distanza[lista:{{_,_}..}]:=Map[Norm,lista]

Distanza[{{2,-3},{4,-1},{2,1},{9,3}}]

Distanza[{{2,-3},{4,-1},{2,1},{9,3,2}}]

Bene abbiamo disabilitato la funzione nel caso di input misto (coppie/triple). Se vogliamo, possiamo usare una caratteristica delle funzioni di Mathematica, ossia l’overloading (cioè la possibilità di definire una funzione con lo stesso nome ma con differenti pattern di ingresso):

??Distanza

Distanza[lista___]:="Input non consentito"

Distanza[{{2,-3},{4,-1},{2,1},{9,3,2}}]

Distanza[{{2,-3},{4,-1},{2,1}}]

Distanza[pippo]

Potremmo volere ancora di più; guardiamo il seguente caso:

Distanza[{{2,-3},{4,-1},{2,1},{9,pippo}}]

che potrebbe essere in alcuni casi voluto; per esempio, posso in seguito specificare quanto vale pippo:

Manipulate[%,{pippo,1,5}]

In realtà, per l’esempio in questione potrebbe essere un effetto indesiderato. Allora possiamo rafforzare il pattern matching restringendo ulteriormente la definizione del pattern ammesso in ingresso. Per fare questo, azzero il contenuto della funzione Distanza perchè devo riscrivere la sua definizione principale:

Clear[Distanza]

Distanza[lista:{{_?NumericQ,_?NumericQ}..}]:=Map[Norm,lista]

Distanza[lista___]:="Input non consentito"

Distanza[{{2,-3},{4,-1},{2,1},{9,pippo}}]

Dunque, ora abbiamo una funzione che opera solo su coppie di numeri.

Le basi della logica funzionale: le funzioni pure

Quando si comincia a scrivere codice funzionale si utilizzano sempre più i pattern, non solo per creare filtri da applicare agli argomenti in input ma anche per selezionare sottoinsiemi di dati su cui applicare una funzione (ad esempio tramite le funzioni Map e simili). Nella maggior parte di questi casi non serve definire una funzione che funga da filtro, ma basta scrivere il filtro stesso tramite una funzione “pura”. La principale differenza tra una funzione “normale” ed una funzione “pura” è che quest’ultima non è salvata in memoria.

Riprendiamo l’esempio della distanza di una serie di punti dall’origine degli assi e aggiungiamo anche il grafico del risultato.

Quit[]

Distanza[lista:{{_?NumericQ,_?NumericQ}..}]:=Map[Norm,lista]

Distanza[lista___]:="Input non consentito"

Aggiungiamo il grafico che rappresenta le linee da ciascun punto verso l’origine degli assi; nel mezzo della linea deve comparire una label con il valore della distanza, qualcosa del tipo:

La funzione Distanza restituisce i valori numerici per le etichette:

punti={{2,3},{-2,-1},{2,7},{9,3}}

Distanza[punti]

Dobbiamo ora aggiungere tutta la parte di grafica. Seguiamo prima un approccio senza le funzioni pure.

Dai punti e le distanze dobbiamo ricavare:
a) il punto blu di grandezza 0.02;
b) l’etichetta con il valore della distanza del punto dall’origine, posizionata nel punto pari alla metà del segmento distanza;
c) la linea dall’origine degli assi al punto assegnato.

Definiamo tre funzioni ausiliari esterne:

Punto[coppia:{_?NumericQ,_?NumericQ}]:={PointSize[0.02],Blue,Point[coppia]}

Linea[coppia:{_?NumericQ,_?NumericQ}]:={Thickness[0.005],Dashing[0.02],Green,Line[{{0,0},coppia}]}

Etichetta[coppia:{_?NumericQ,_?NumericQ},distanza_?NumericQ]:={Red,Text[ToString[distanza],coppia/2]}

Ora definiamo la funzione complessiva in termini delle precedenti:

Distanza1[lista:{{_?NumericQ,_?NumericQ}..}]:=Graphics[
Table[{Punto[lista[[i]]],Linea[lista[[i]]],Etichetta[lista[[i]],N[Norm[lista[[i]]]]]},{i,Length[lista]}]]

Distanza1[punti]

Ma possiamo constatare che al di fuori del corpo Distanza1, le tre funzioni ausiliare non servono e pertanto risulta uno spreco di memoria averle definite esplicitamente. Possiamo creare tre funzioni pure che “vivono e muoiono” soltanto nel tempo necessario al loro compito.

Distanza[lista:{{_?NumericQ,_?NumericQ}..}]:=Graphics[MapThread[{{Blue,PointSize[0.02],Point[#1] },{Thickness[0.005],Dashing[0.02],Green,Line[{{0,0},#1}]},{Red,Text[ToString[#2],#1/2]}}&,{punti,N[Map[Norm,lista]]}]]

Distanza[punti]

Le basi della logica funzionale: ragionare per funzioni

In questo esempio mostriamo come si può procedere passo passo ad una soluzione funzionale completa tramite il ragionamento sul problema e sulla sua soluzione generalizzata.

Il problema consiste nel dover sostituire i valori simbolici di una data espressione con una funzione di tali simboli

exp = (x^3)+(((1+z))^2)

Bisogna sostituire x e z con i valori sin(x) e sin(z).
Primo modo di procedere: vedendo l’espressione, individuo la posizione dei simboli e li sostituisco

TreeForm[exp]

MapAt[Sin,exp,{{1,1},{2,1,2}}]

Ma se non posso vedere fisicamente l’espressione? Allora mi calcolo la posizione dei due simboli

Position[exp,x]

Position[exp,z]

MapAt[Sin,exp,Join[Position[exp,x],Position[exp,z]]]

E se l’espressione contiene un altro simbolo e non z?

Dal suo help scopro che Position richiede un pattern al secondo posto:

?Position

Dunque basta che scrivere il pattern che definisce i simboli:

Position[exp,_Symbol]

Ci sono troppi risultati ... perchè? Sempre dall’help scopro che Position considera anche il livello zero di ciascuna espressione o sotto espressione. Dunque, se chiedo la posizione di un simbolo mi darà anche la posizione dei simboli che formano le funzioni di exp:

TreeForm[exp]

Allora inibisco il controllo sui simboli delle head delle espressioni e sotto escpressioni (livello zero):

Position[exp,_Symbol,Heads->False]

MapAt[Sin,exp,Position[exp,_Symbol,Heads->False]]

E se su una qualsiasi espressione voglio applicare una qualsiasi funzione al posto dei simboli e non necessariamente “sin”? 
Posso creare una funzione e generalizzare sia l’espressione sia la funzione da applicare:

CambiaVariabili[funzione_,espressione_]:=MapAt[funzione,espressione,Position[espressione,_Symbol, Heads->False]]

CambiaVariabili[Log,2x+x (w^3)+2(x^r)+y+t+w]

Un’altra soluzione si ha con Replace:

CambiaVariabili1[funzione_,espressione_]:=Replace[espressione,x_Symbol:>funzione[x],Infinity]

CambiaVariabili1[Log,2x+x (w^3)+2(x^r)+y+t+w]

Le basi della logica funzionale: ragionare per funzioni

In questo secondo esempio mostriamo come, ragionando istintivamente per “procedure” (ossia immaginando sempre che la soluzione sia costruita elemento per elemento), ci si può abituare ad una visione ristretta sul modo di trovare una soluzione.

Il problema consiste nel dover generare una lista di lunghezza definita con interi casuali compresi nell’intervallo {-10, 10} ad esclusione dello zero.

Ragionando immediatamente per procedure, penso di costruire una lista di valori random e poi eliminare gli eventuali zeri sostituendoli con altri random non nulli. 
Una prima soluzione potrebbe essere:

NonNulli[n_]:=
Module[{a},
a =RandomInteger[{-10,10},{n}];
While[MemberQ[a,0], a=ReplacePart[a, RandomInteger[{-10,10}], Position[a, 0]]];
Return[a]]

NonNulli[300]

MemberQ[NonNulli[3000000],0]

AbsoluteTiming[MemberQ[NonNulli[3000000],0]]

Proviamo un approccio diverso

1)

NonNulli1[n_]:=Table[(((-1))^(Random[Integer]))RandomInteger[{1,10}],{n}]

AbsoluteTiming[MemberQ[NonNulli1[3000000],0]]

2)

NonNulli2[n_]:=Table[RandomChoice[{-1,1}]*RandomInteger[{1,10}],{n}]

AbsoluteTiming[MemberQ[NonNulli2[3000000],0]]

3)

NonNulli3[n_]:=RandomChoice[{-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9,10},n]

AbsoluteTiming[MemberQ[NonNulli3[3000000],0]]

Come si evince da questo ultimo esempio, ogni qualvolta si riesce ad evitare un ciclo (es. Table) il tempo di calcolo si riduce notevolmente :-)

Le basi della logica funzionale: gli script one-line

Negli esempi della slide precedente uno dei vantaggi offerti dall’approccio funzionale è che in realtà non si ha sempre bisogno di usare variabili intermedie per memorizzare i risultati parziali. Sfruttando il concetto secondo cui le funzioni si applicano ai dati ed il risultato fornisce ancora dei dati su cui applicare altre funzioni, si possono creare righe di codice molto sintetico e perciò molto veloce.
Nel paradigma funzionale teoricamente tutti gli algoritmi si possono scrivere come script one-line, ossia tutto il codice si può sintetizzare in un’unica istruzione. Questo è possibile grazie al fatto che secondo tale paradigma in realtà non sono necessarie variabili di appoggio e non sono necessari cicli. Sebbene questo punto di vista sia condivisibile in principio, nella realtà questa situazione non capita spesso e soprattutto non è semplice da ottenere se non in casi molto semplici. Ad ogni modo è bene abituarsi alla logica one-line almeno come modello di esempio, così si impara a rendere il proprio codice sempre più sintetico e vicino alla logica funzionale. 
Vediamo un piccolo trucco per convertire più righe di codice in una sola riga.

Come scrivere codice one-line:

InstallJava[]

data=Import["http://www.bls.gov/web/laus/laumstrk.htm",{"Data"}]; (* importa la pagina html *)

data2=Cases[data,{_Integer,_String,_Real},Infinity];  (* Estraiamo i soli dati{rank, STATE, rate} *)

results=data2[[All,{2,3}]]; (* eliminiamo il rank *)

SortBy[results,First]; (* ordiniamo alfabeticamente *)

Grid[results,Alignment->Left,Frame->All,Background->LightYellow,BaseStyle->{"Menu"}]

Mettiamo tutto insieme in una sola riga:

Grid[SortBy[Cases[data,{_Integer,_String,_Real},Infinity][[All,{2,3}]],First],Alignment->Left,Frame->All,Background->LightYellow,BaseStyle->{"Menu"}]

Conclusioni

Nonostante sembra che la logica funzionale abbia una curva di apprendimento più ripida (almeno a detta di molti utenti), una volta raggiunta una certa predisposizione al ragionamento per funzioni si riesce a scrivere codice Mathematica con una notevole sintesi, eleganza stilistica e leggibilità del codice che sono impagabili tanto per piccoli algoritmi quanto per applicazioni complesse.

Comunque, si tenga conto che Mathematica - pur essendo un linguaggio funzionale - mette a disposizione set di funzioni dedicati ai vari approcci di programmazione:

Procedural Programming
Rule-Based Programming
Graph Programming
CUDA Programming

Dunque un’altra delle sua caratteristiche è che si presenta come un linguaggio pluriparadigmatico per soddisfare diverse esigenze anche dal punto di vista dello stile di programmazione.