Molto spesso, per imparare un nuovo linguaggio di programmazione, si esaminano alcuni problemi matematici. Questo avviene per due motivi: il primo è motivo deriva dal fatto che molti piccoli problemi matematici sono molto semplici e quindi non aggiungono livelli di complessità all’attuale nostro problema di imparare un particolare linguaggio di programmazione. Il secondo motivo è dato dal fatto che questo approccio consente di imparare in modo più efficace i costrutti di base della programmazione nel linguaggio scelto: cicli, istruzioni condizionali, assegnazione di valori, visualizzazione del risultato e così via.
Un sito interessante che raccoglie molti di questi problemi matematici, in ordine di difficoltà crescente, è “Project Euler .net” (http://projecteuler.net). Potete registrarvi al sito per provare a dare le vostre soluzioni. Quando fornirete una soluzione corretta, vedrete nel vostro “pannello” dei problemi le soluzioni trovate e potrete anche visualizzare un file PDF contenente una spiegazione dettagliata della soluzione proposta.
Utilizzerò pertanto qualcuno di questi problemi per costruire il nostro “vocabolario” delle istruzioni di F#. Il fatto che il sito abbia il suffisso “.net” è solamente un caso: non ha alcuna attinenza con il Framework .NET 
Il primo problema consiste nell’esaminare e sommare tra loro tutti i multipli di 3 e di 5 in un intervallo di numeri naturali che va da 1 a “x”. Per esempio, tra 1 e 9, la somma dei multipli di 3 e 5 è pari a 23 (= 3+5+6+9).
Trovare la somma di tutti i numeri multipli di 3 e di 5, tra 1 e 999.
Possiamo risolvere questo problema in almeno due modi (ma probabilmente anche in molti altri). In entrambi i casi otteniamo il numero 233168.
La prima soluzione è la seguente:
#light
let rec sum_mul xs =
match xs with
| [] -> 0
| y::ys when y % 3 = 0 || y % 5 = 0 -> y + sum_mul ys
| y::ys -> sum_mul ys
let sum = sum_mul [1 .. 999]
printfn "%d" sum
Esaminiamo come funziona questa prima soluzione.
La direttiva #light permette di scrivere il codice in modo più semplice, senza le parole chiave begin … end e senza altri caratteri che indicano il termine delle righe di istruzione (come il “;” di C#, per esempio). I cicli o i blocchi di codice sono definiti dall’indentazione del codice (cioè dai rientri), mentre il termine delle istruzioni è semplicemente riconosciuto dalla presenza di spazi e di ritorni a capo.
Nella seconda riga abbiamo inserito una funzione ricorsiva, denominata sum_mul, che accetta il parametro xs.
Nelle righe dalla 3^ alla 6^ c’è un esempio di pattern matching: un metodo elegante per gestire varie alternative (come uno switch o un select case). Il programma confronta xs con alcuni pattern, ciascuno scritto in una riga separata e preceduti dal simbolo “|” (pipe). Nel primo caso il confronto ha successo quando xs è una lista vuota e in tal caso sum_mul restituisce 0 (zero).
Negli altri casi, xs corrisponde a una lista, in cui il primo elemento (la testa della lista) viene chiamato y e il resto della lista (la coda della lista) viene chiamato ys.
Se y è divisibile per 3 o per 5 (utilizzando l’operatore modulo: %) aggiungiamo il numero al risultato e poi eseguiamo la stessa funzione ricorsivamente per la coda della lista. In caso contrario, semplicemente saltiamo il valore di testa e continuiamo ad esaminare la coda della lista.
Nell’8^ riga chiamiamo effettivamente la funzione sum_mul passando una lista come argomento. Questa lista è composta da tutti i numeri interi da 1 a 999 (o qualsiasi altro numero abbiate fissato come numero finale).
Per eseguire il programma e visualizzare il risultato potete premere F5 come al solito (l’istruzione printfn stamperà il risultato in una finestra analoga al prompt di comandi), oppure potete evidenziare la porzione di codice da eseguire e premere contemporaneamente ALT + INVIO. In quest’ultimo caso, il programma sarà eseguito e il risultato sarà visibile nella finestra “F# interactive” che comparirà nella parte inferiore del video.
La seconda soluzione invece è maggiormente ottimizzata:
#light
let sum_mult max step =
let n = max / step
step*n*(n + 1)/2
let max = 999
let sum2 =
sum_mult max 3 + sum_mult max 5 - sum_mult max 15
printfn "%d" sum2
Partendo dal presupposto che stiamo sommando tutti i multipli di 3 e di 5, possiamo anche effettuare una semplice operazione per trovare tutti i multipli dell’uno e dell’altro valore, invece di provare tutti i valori nell’intervallo considerato (da 1 a 999). In tal caso dobbiamo anche sottrarre tutti i multipli di 15, perché 15 è divisibile sia per 3 sia per 5, e quindi dobbiamo evitare di contare tali valori per due volte.
Ricordando che la somma dei primi n numeri interi è uguale a n*(n+1)/2, possiamo utilizzare questa semplice formula per eseguire l’operazione desiderata, prima con il numero 3, poi con il numero 5 e infine con il numero 15.
Nella 2^ linea definiamo la funzione sum_mult che prende due argomenti interi: max e step.
Nella linea successiva, definiamo un identificatore locale denominato n, il cui ambito di visibilità è limitato all’interno della funzione sum_mult.
Il resto del codice è estremamente semplice, dato che applichiamo la formula sopra indicata.
Confrontando la complessità computazionale dei due programmi (chiamata “O grande”), troviamo che nel primo caso abbiamo una complessità O(n), mentre nel secondo caso abbiamo O(1). Nel secondo caso, quindi, la complessità (e la durata di esecuzione) è indipendente dal numero di valori da esaminare (in questo caso 999).
N.B. lo spunto per questo post e l’informazione sul sito Project Euler .net è stato gentilmente concesso da Claudio Cherubino (http://www.fsharp.it e http://www.claudiocherubino.it/). Grazie!
L'Angolo di SuperMario 