Alcuni esercizi in OCaml

Alcuni esercizi in OCaml
Corso di Linguaggi di Programmazione
Vincenzo Ciancia ISTI/CNR Pisa
[email protected]
Definiamo un tipo per le sequenze di interi
# type s = E | I of (int * s);;
type s = E | I of (int * s)
# let rec length x = match x with E > 0 | I(n,y) > 1 + (length y);;
val length : s > int = <fun>
# length (I(3,I(4,E)));;
: int = 2
2
Esercizio
Definire la funzione
accumula : (int > int > int) > int > S > int
accumula f base I(n1,I(n2,I(n3,....,I(nk,E)))) =
f n1 (f n2 (f n3 (...(f nk base))))
# accumula (fun x y > x + y) 0 (I(3,I(4,I(2,E))));;
: int = 9
Poi definire la funzione “sum” usando accumula.
3
Soluzione
# let rec accumula f base x = match x with E > base | I (n,y) > f n (accumula f base y);;
val accumula : (int > 'a > 'a) > 'a > s > 'a = <fun>
# let sum = accumula(+) 0;;
val sum : s > int = <fun>
# sum (I(1,I(2,I(5,E))));; : int = 8
4
Esercizio: zip
Definite la funzione
zip : 'a list > 'b list > ('a * 'b) list
Date due liste di uguale lunghezza, zip l1 l2 crea la lista di coppie
fatta dagli elementi di l1 e l2
# zip [1;2] [3;4];;
: (int * int) list = [(1, 3); (2, 4)]
5
Soluzione
Soluzione 1:
# let rec zip l1 l2 = match (l1,l2) with
(x::xs,y::ys) > (x,y)::(zip xs ys)
| ([],[])> []
Patter matching non esaustivo!
Soluzione 2:
# let rec zip l1 l2 = match (l1,l2) with
(x::xs,y::ys) > (x,y)::(zip xs ys)
| _ > [];;
6
Esercizio: unzip
La funzione inversa
unzip :: ('a * 'b) list > ('a list * 'b list)
7
Soluzione
Soluzione 1:
# let rec unzip l = match l with [] > ([],[])
| (x,y)::l' > match unzip l' with
(xs,ys) > (x::xs,y::ys);;
Soluzione 2:
# let rec unzip l = let aux (x,y) (xs,ys) = (x::xs,y::ys) in
match l with [] > ([],[]) | (x,y)::l' > aux (x,y) (unzip l');;
8
If then else
Uno shortcut al pattern matching: invece di scrivere match x with true > RAMO1 | false > RAMO2
posso scrivere
if x then RAMO1 else RAMO2
9
Esercizio: filter
Scrivete la funzione
filter : ('a > bool) > 'a list > 'a list il risultato atteso di filter pred l
è la lista di tutti gli elementi di l che soddisfano il predicato pred.
10
Soluzione
Soluzione
# let rec filter pred l =
match l with
[] > []
| x::xs > if pred x then x::(filter pred xs) else filter pred xs;;
Esempio:
# let positive = filter (fun x > x >= 0);;
val positive : int list > int list = <fun>
# positive [1;3;3;4;5;6];;
: int list = [3; 5; 6]
Notare che nella definizione di positive non passo alcun parametro di tipo lista.
11
Esercizio: partition
Definire la funzione
partition : ('a > bool) > 'a list > 'a list * 'a list Il risultato di partition pred l è una coppia di liste, la prima contiene tutti gli elementi che soddisfano il predicato pred, la seconda quelli che non lo soddisfano
12
Soluzione
# let rec partition pred l =
let aux x fst_or_snd (l1,l2) = if fst_or_snd then (x::l1,l2) else (l1,x::l2) in
match l with
[] > ([],[])
| x::xs > aux x (pred x) (partition pred xs);;
# partition (fun x > x >= 0) [1;3;4;3;5];;
: int list * int list = ([3; 4; 5], [1; 3])
13
Soluzione 2
# let rec partition pred l =
match l with [] > ([],[])
| x::xs >
match (pred x,partition pred xs) with
(true,(r1,r2)) > (x::r1,r2)
| (false,(r1,r2)) > (r1,x::r2);;
# partition (fun x > x >= 0) [1;3;4;3;5];;
: int list * int list = ([3; 4; 5], [1; 3])
14

Download Report