Tipi di dati e matching
Liste linkate
Così come Perl, OCaml ha il supporto per le liste implementato nel linguaggio. Tutti gli elementi di una lista in OCaml devono essere dello stesso tipo. Per scrivere una lista, usate:
[1; 2; 3]
(Si notino i punti e virgola, NON virgole).
[]
è la lista vuota.
Una lista ha un'head (testa) (il primo elemento) ed una tail
(coda) (il resto degli elementi). La testa è un elemento, e la coda è
una lista, così nell'esempio sopra la testa è l'intero 1
mentre la
coda è la lista [2; 3]
.
Un modo alternativo di scrivere una lista è quello di usare l'operatore
cons head :: tail
. Così i seguenti modi di scrivere una lista sono
esattamente equivalenti:
[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]
1 :: 2 :: 3 :: []
Perché menziono l'operatore cons? Bene, è utile quando cominciamo a fare pattern matching sulle liste, riguardo la qual cosa parlerò sotto.
Il tipo di una lista linkata
Il tipo di una list linkata di interi è int list
, ed in generale il
tipo di una lista linkata di foo
è foo list
.
Ciò implica che tutti gli elementi di una lista linkata devono avere il
medesimo tipo. Ma il tipo può essere polimorfico (cioè 'a list
), che è
davvero utile se volete scrivere funzioni generiche che operano su
"liste di checchessia". (Ma si noti: 'a list
non significa che
ciascun elemento preso singolamente ha un diverso tipo - non potete
comunque usare questo per costruire una lista contenente, diciamo, int e
string insieme. Significa che il tipo degli elementi è qualsiasi, ma
tutti del medesimo qualsiasi tipo.)
La funzione length
definita come parte del modulo di OCaml List
è un
buon esempio di ciò. Non importa se le lista contiene interi o stringhe
o oggetti o piccoli animali da pelliccia, la funzione List.length
può
comunque essere chiamata su di essa. Il tipo di List.length
è dunque:
List.length : 'a list -> int
Strutture
C e C++ hanno il concetto di una semplice struct
, abbreviazione per
"structure" (struttura). Java ha le classi che possono essere utilizzate
con effetti simili, sebbene molto più laboriosamente.
Considerate questa semplice struttura C:
struct pair_of_ints {
int a, b;
};
Il più semplice equivalente a ciò in OCaml è una tupla come (3, 4)
che ha il tipo int * int
. Diversamente dalle liste, le tuple possono
contenere elementi di differenti tipi, così ad esempio
(3, "hello", 'x')
ha tipo int * string * char
.
Un modo alternativo lievemente più complesso di scrivere una struttura C è quello di utilizzare un record. I record, come le struct C, vi consentono di dare nomi agli elementi. Le tuple non vi lasciano dare nomi agli elementi, ma dovete invece ricordare l'ordine in cui essi appaiono. Ecco l'equivalente della nostra struct C sopra:
type pair_of_ints = { a : int; b : int }
Questo definisce il tipo, ed ecco come effettivamente creiamo oggetti di questo tipo:
{ a=3; b=5 }
Si noti che usiamo :
nella definizione di tipo mentre usiamo =
quando creiamo
oggetti di questo tipo.
Seguono alcuni esempi di ciò digitati nel toplevel:
# type pair_of_ints = { a : int; b : int };;
type pair_of_ints = { a : int; b : int; }
# {a=3; b=5};;
- : pair_of_ints = {a = 3; b = 5}
# {a=3};;
Error: Some record fields are undefined: b
Così OCaml non vi consente di lasciare nella vostra struttura dei campi indefiniti.
Varianti (union qualificate ed enum)
Una "union qualificata" ("qualified union") non esiste realmente in C, sebbene vi sia il supporto per essa nel compilatore gcc. Ecco il pattern comunemente usato per una union qualificata in C:
struct foo {
int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
union {
int i; // If type == TYPE_INT.
int pair[2]; // If type == TYPE_PAIR_OF_INTS.
char *str; // If type == TYPE_STRING.
} u;
};
Dovrei pensare che l'abbiamo visto tutti, e non è un bel vedere. Per
cominciare non è sicuro: il programmatore potrebbe commettere uno
sbaglio ed usare accidentalmente, diciamo, il campo u.i
quando di
fatto nella sua struttura è stata immagazzinata una stringa. Inoltre il
compilatore non può facilmente verificare se in un'istruzione switch
sono stati verificati tutti i possibili tipi (si potrebbe invece
utilizzare un tipo enum
per risolvere questo particolare problema). Il
programmatore potrebbe dimenticare di impostare il campo type
, il che
avrebbe per effetto ogni sorta di giochi e divertimenti. Inoltre è
ingombrante.
Ecco l'equivalente elegante e conciso in OCaml:
type foo = Nothing | Int of int | Pair of int * int | String of string
Quella è la definizione del tipo. La prima parte di ciascun |
separato a parte è detto costruttore.
Esso può essere chiamata in qualunque
modo, purché cominci con una lettera maiuscola. Se il costruttore può
essere usato per la definizione di un valore, è seguito dalla parte
of type
, dove type comincia sempre per lettera minuscola. Nell'esempio
sopra, Nothing è usato come costante e gli altri costruttori sono usati
con dei valori.
Per creare effettivamente cose di questo tipo scrivereste:
Nothing
Int 3
Pair (4, 5)
String "hello"
(* &c. *)
Ciascuna di queste espressioni ha tipo foo
.
Si noti che si usa of
nello scrivere la definizione del tipo, ma NON
nello scrivere elementi di quel tipo.
Per estensione, una semplice enum
di C definita come:
enum sign { positive, zero, negative };
può essere scritta in OCaml come:
type sign = Positive | Zero | Negative
Varianti ricorsive (utilizzate per gli alberi)
Le varianti possono essere ricorsive, e l'utilizzo comune di ciò è per la definizione di strutture ad albero. Qui è davvero dove la potenza espressiva dei linguaggi funzionali li contraddistingue:
type binary_tree = Leaf of int | Tree of binary_tree * binary_tree
Ecco alcuni alberi binari. Per fare pratica, provate a disegnarli sulla carta.
Leaf 3
Tree (Leaf 3, Leaf 4)
Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))
Varianti parametrizzate
L'albero binario della sezione precedente ha interi a ciascuna foglia, ma se volessimo descrivere la forma di un albero binario, e soltanto poi decidere esattamente che cosa immagazzinare in ciascuna foglia? Possiamo farlo usando una variante parametrizzata (o polimorfica), come questa:
# type 'a binary_tree =
| Leaf of 'a
| Tree of 'a binary_tree * 'a binary_tree;;
type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree
Questo è un tipo generale. Il tipo specifico che immagazzina interi in
ciascuna foglia è chiamato int binary_tree
. In modo simile il tipo
specifico che conserva stringhe in ciascuna foglia è chiamato
string binary_tree
. Nel prossimo esempio digitiamo alcune istanze nel
top-level e consentiamo al sistema di inferenza dei tipi di mostrare i
tipi per noi:
# Leaf "hello";;
- : string binary_tree = Leaf "hello"
# Leaf 3.0;;
- : float binary_tree = Leaf 3.
Notate come il nome del tipo sia di dietro. Confrontate ciò con i nomi
dei tipi per le liste, p.e. int list
etc.
Non è in effetti una coincidenza che 'a list
è scritto "di dietro"
nello stesso modo. Le liste sono tipi varianti parametrizzati in modo
semplice con la seguente definizione, leggermente strana:
type 'a list = [] | :: of 'a * 'a list (* non è codice OCaml reale *)
Di fatto la definizione sopra non è valida per la compilazione. Ecco una definizione sostanzialmente equivalente:
# type 'a list = Nil | :: of 'a * 'a list;;
Error: Syntax error
# Nil;;
Error: Unbound constructor Nil
# 1 :: Nil;;
Error: This variant expression is expected to have type int list
The constructor Nil does not belong to type list
# 1 :: 2 :: Nil;;
Error: This variant expression is expected to have type int list
The constructor Nil does not belong to type list
Ricordate quando in precedenza avevamo detto che le liste potevano
essere scritte in due modi, con il semplice "zucchero sintattico" di
[1; 2; 3]
o più formalmente come 1 :: 2 :: 3 :: []
. Se osservate la
definizione di 'a list
scritta sopra, potreste riuscire a scorgere la
ragione della definizione formale.
Liste, strutture e varianti - sommario
Nome in OCaml Esempio di definizione di tipo Esempio di utilizzo
lista int list [1; 2; 3]
tupla int * string (3, "hello")
record type pair = { a = 3; b = "hello" }
{ a: int; b: string }
variante type foo =
| Int of int Int 3
| Pair of int * string
variante type sign =
| Positive Positive
| Zero Zero
| Negative
variante type 'a my_list =
parametrizzata | Empty Cons (1, Cons (2, Empty))
| Cons of 'a * 'a my_list
Pattern matching (sui tipi di dati)
Una Caratteristica Davvero Forte dei linguaggi funzionali è dunque la possibilità di disassemblare le strutture dati e fare pattern matching sui dati. Anche questa non è realmente una caratteristica "funzionale" - si potrebbe immaginare la comparsa di una variazione di C che consenta di fare ciò - ma nondimeno è una Caratteristica Forte.
Cominciamo con una necessità di un programma reale: vorrei rappresentare
semplici espressioni matematiche come n * (x + y)
e moltiplicarle
simbolicamente così da ottenere n * x + n * y
.
Definiamo un tipo per queste espressioni:
# type expr =
| Plus of expr * expr (* means a + b *)
| Minus of expr * expr (* means a - b *)
| Times of expr * expr (* means a * b *)
| Divide of expr * expr (* means a / b *)
| Value of string (* "x", "y", "n", etc. *);;
type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Value of string
L'espressione n * (x + y)
sarebbe scritta:
# Times (Value "n", Plus (Value "x", Value "y"));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))
Scriviamo una funzione che stampi
Times (Value "n", Plus (Value "x", Value "y"))
come qualcosa che
somigli più a n * (x + y)
. Sto in realtà per scrivere due funzioni,
una che converta l'espressione in una stringa comoda da leggere, ed una
che la stampi (il motivo è che potrei voler scrivere la stessa stringa
in un file e non vorrei solo per questo ripetere l'intera funzione).
# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;
val to_string : expr -> string = <fun>
# let print_expr e =
print_endline (to_string e);;
val print_expr : expr -> unit = <fun>
(NB: L'operatore ^
concatena stringhe.)
Ecco la funzione di stampa in azione:
# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y))
- : unit = ()
La forma generale per il pattern matching è:
match value with
| pattern -> result
| pattern -> result
...
Il pattern sulla sinistra può essere semplice, come nella funzione
to_string
sopra, o complesso e annidato. Il prossimo esempio è la
nostra funzione per moltiplicare espressioni nella forma n * (x + y)
o
(x + y) * n
e per questo utilizzeremo un pattern annidato:
# let rec multiply_out e =
match e with
| Times (e1, Plus (e2, e3)) ->
Plus (Times (multiply_out e1, multiply_out e2),
Times (multiply_out e1, multiply_out e3))
| Times (Plus (e1, e2), e3) ->
Plus (Times (multiply_out e1, multiply_out e3),
Times (multiply_out e2, multiply_out e3))
| Plus (left, right) ->
Plus (multiply_out left, multiply_out right)
| Minus (left, right) ->
Minus (multiply_out left, multiply_out right)
| Times (left, right) ->
Times (multiply_out left, multiply_out right)
| Divide (left, right) ->
Divide (multiply_out left, multiply_out right)
| Value v -> Value v;;
val multiply_out : expr -> expr = <fun>
Eccola in azione:
# print_expr(multiply_out(Times (Value "n", Plus (Value "x", Value "y"))));;
((n * x) + (n * y))
- : unit = ()
Come funziona la funzione multiply_out
? La chiave è nei primi due
pattern. Il primo pattern è Times (e1, Plus (e2, e3))
che coincide con
espressioni della forma e1 * (e2 + e3)
. Guardate ora a destra del
primo pattern match, e convincetevi che è l'equivalente di
(e1 * e2) + (e1 * e3)
.
Il secondo pattern fa la stessa cosa, ma per espressioni della forma
(e1 + e2) * e3
.
I restanti pattern non cambiano la forma dell'espressione, ma chiamano
ricorsivamente in modo cruciale la funzione multiply_out
sulle loro
sottoespressioni. Questo assicura che vengano moltiplicate anche tutte
le sottoespressioni all'interno dell'espressione (se voleste soltanto
moltiplicare in un'espressione gli elementi di livello più alto,
potreste sostituire tutti i restanti pattern con una semplice regola
e -> e
).
Possiamo fare il contrario (cioè fattorizzare subespressioni comuni)? Certo che possiamo! (Ma è un po' più complicato). La seguente versione funziona solo per l'espressione di livello superiore. La potreste certamente estendere per farla collimare con tutti i livelli di un'espressione e con casi più complessi:
# let factorize e =
match e with
| Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 ->
Times (e1, Plus (e2, e4))
| Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 ->
Times (Plus (e1, e3), e4)
| e -> e;;
val factorize : expr -> expr = <fun>
# factorize (Plus (Times (Value "n", Value "x"),
Times (Value "n", Value "y")));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))
La funzione factorize scritta sopra introduce un altro paio di
caratteristiche. È possibile aggiungere quelle che sono conosciute come
guardie ad ogni pattern match. È una guardia il condizionale che
segue il when
, ed essa significa che il pattern match si ha soltanto
se il pattern coincide e la condizione nella clausola introdotta da
when
è soddisfatta.
match value with
| pattern [ when condition ] -> result
| pattern [ when condition ] -> result
...
La seconda caratteristica è l'operatore =
che indaga l'"uguaglianza
strutturale" fra due espressioni. Il che significa che va a verificare
in ciascuna espressione ricorsivamente che esse siano esattamente le
medesime a tutti i livelli sottostanti.
OCaml può verificare durante la compilazione che nei pattern siano state
coperte tutte le possibilità. Ho modificato la definizione di tipo di
type expr
sopra aggiungendo una variante Product
:
# type expr = Plus of expr * expr (* means a + b *)
| Minus of expr * expr (* means a - b *)
| Times of expr * expr (* means a * b *)
| Divide of expr * expr (* means a / b *)
| Product of expr list (* means a * b * c * ... *)
| Value of string (* "x", "y", "n", etc. *);;
type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Product of expr list
| Value of string
Ho quindi ricompilato la funzione to_string
senza modificarla. OCaml
ha riportato il seguente avviso:
# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Product _
val to_string : expr -> string = <fun>