F# - Liste

Al giorno d'oggi programmando, molto spesso si imbatte nella necessità di raggruppare più elementi dello stesso tipo. Proprio in questi casi in F# vengono usate le liste, per memorizzare queste sequenze di elementi. Nei linguaggi di programmazione procedurale, come Java e C++, queste strutture dati vengono chiamate liste concatenate, perché tra un elemento della lista e il suo successivo esiste un collegamento.
Oltre alle liste esiste un'altra struttura dati per raggruppare più elementi dello stesso tipo ed viene chiamata array, però gli array hanno il grosso svantaggio di essere limitati, perché una volta creato non può modificare la sua lunghezza.
Ma come segue dal titolo dell'articolo, ci occuperemo dello studio delle liste e non degli array, per cui andiamo a vedere i modi in cui possono essere create le liste:

let lista = [];;
let lista2 = 0::1::2::lista;;
let lista3 = [3;4;5;6];;
let lista4 = lista2 @ lista3;;

Con queste righe di codice abbiamo, sostanzialmente, creato 4 liste diverse. La prima lista non è altro che una lista vuota, ovvero una lista che non contiene elementi e quindi è lunga 0. Nella seconda riga di codice, invece, abbiamo usato l'operazione di concatenazione di elementi ad una lista, aggiungendo in testa alla prima lista gli elementi 0,1 e 2 e il risultato l'abbiamo scritto in lista2.

L'operazione di concatenazione può essere usato soltanto per aggiungere elementi in testa alla lista e come ultimo elemento della concatenazione deve per forza essere una lista.

Con la terza riga del codice abbiamo creato una nuova lista, inserendo direttamente gli elementi al suo interno, mentre la quarta lista l'abbiamo creata mediante la concatenazione della seconda e della terza lista, visto che l'operatore @ permette di concatenare due liste, mettendo per primi gli elementi della prima lista, seguiti da quelli della seconda lista.
Molto spesso, lavorando con le liste sorge la necessità di suddividere la lista in testa e coda, dove la testa rappresenta il primo elemento della lista, mente la coda rappresenta il resto della lista. Di seguito è riportato un esempio in cui viene fatto ciò:

let lista = [1;2;3;4];;
let testa::coda = lista;;

In questi modo abbiamo detto all'interprete di F# di assegnare al nome testa il primo elemento di lista e di assegnare la coda di lista al nome coda. Fare così è equivalente a spezzettare la lista originale in testa e coda, che spesso si rivela molto utile quando si scrivono funzioni ricorsive, che devono dare determinate operazioni sulle liste.
Proviamo a vedere un breve esempio di funzione, che determina la lunghezza di una lista. L'idea risolutivo è quello di spezzettare la lista in testa e coda, dopodiché aggiungere 1 alla lunghezza della coda della lista:

let rec lunghezza lst =
    match lst with
    | [] -> 0
    | x::xs -> 1 + (lunghezza xs);;

Come possiamo vedere, per la scrittura della funzione abbiamo usato il pattern matching, in cui confrontiamo la lista, passata come argomento della funzione, con la lista vuota e con una lista, che contiene almeno un elemento. Con la scrittura x::xs viene la lista viene spezzettata, come è stato spiegato in precedenza, per cui richiamando la funzione stessa, passandogli xs come argomento, è equivalente al richiamo della funzione lunghezza sulla coda della lista lst. In questo modo primo o poi si arriva alla situazione in cui la lista lst è uguale alla lista vuota e quindi si chiude il ciclo. Ma aggiungere ad ogni passaggio 1 al risultato equivale al contare in quanti passaggi la lista si svuota, per cui viene trovata la lunghezza della lista.
Se proviamo ad analizzare i vari passaggi che esegue l'interprete di F# per restituire il risultato della funzione in un esempio concreto otteniamo il seguente risultato:

lunghezza [1;2;3;4]
1+(lunghezza [2;3;4])
1+(1+(lunghezza [3;4]))
1+(1+(1+(lunghezza [4])))
1+(1+(1+(1+(lunghezza []))))
1+(1+(1+(1+0)))
1+(1+(1+1))
1+(1+2)
1+3
4

Dalla traccia riportata in alto si può vedere molto bene come ad ogni passaggio viene aumentato il numero dei 1+, mentre dalla lista viene eliminato il primo elemento. Inoltre, vediamo che il risultato restituito dalla funzione è 4, che è proprio la lunghezza della lista passata come argomento alla funzione, quindi possiamo affermare che la funzione è corretta.