Programmazione Funzionale

Programmazione Funzionale
Esercizi sulle liste
Davide Mottin - Themis Palpanas
April 16, 2014
1/15
Ripasso
Costruire una funzione ricorsiva
Liste
Enumerazione di insiemi
Liste strettamente crescenti
La funzione map
La funzione filter
Insieme delle parti
Sottoinsiemi di determinata cardinalit`a
Sommario
2/15
Suggerimenti per “pensare” ricorsivo
1. Leggere attentamente il problema da risolvere
2. Pensare al caso pi`
u banale nel quale la funzione da costruire
sia definita e per il quale possiamo dare il risultato
immediatamente (Suggerimento: in molte occasioni il caso
base `e il minimo di un insieme, se ordinato, per esempio lo 0
per i numeri naturali, [] per le liste, ”” per le stringhe)
3. Pensare a quale valore la funzione assume nel caso ci si trovi
di fronte all’input (caso) base, senza preoccuparci delle
chiamate ricorsive
4. Pensare al caso ricorsivo in questo modo:
4.1 supporre di sapere risolvere il problema nel caso
immediatamente pi`
u semplice
4.2 avendo gi`a il risultato del caso semplice costruire il caso pi`
u
complesso manipolando il risultato della chiamata ricorsiva
opportunamente
In un certo senso si pensa tutto in maniera bottom-up ossia dal
basso verso l’alto.
Ripasso
3/15
Suggerimenti per “pensare” ricorsivo
Prendiamo per esempio la funzione che conta il numero di elementi
in una lista
l e t rec l e n g t h = f u n c t i o n
[] − > 0
| x : : x s −> 1 + l e n g t h x s ; ;
I
I
Ripasso
caso base: la lista pi`
u piccola pensabile `e la lista vuota,
quindi se troviamo [] allora sappiamo PER DEFINIZIONE che
la lunghezza di una lista vuota `e 0 (nota che non abbiamo
avuto bisogno di nessun altra operazione, lo sappiamo senza
doverlo calcolare)
caso ricorsivo: allora vediamo di estrarre un elemento dalla
lista e supponiamo di SAPERE che la funzione length xs
restituisce la lunghezza della lista xs, perch´e un oracolo ci ha
detto che lo sappiamo calcolare. Cosa dobbiamo fare per
ottenere la lunghezza della lista x::xs dato in input la
lunghezza di xs? Banalmente dobbiamo aggiungere 1 perch´e
abbiamo trovato un elemento in pi`
u.
4/15
Enumerazione di insiemi
Costrure una funzione enumerate:’a list -> (’a * int)
list che preso in input una lista costruisca la lista di coppie
formate da un elemento della lista in input e da un numero
progressivo che rappresenta l’indice di quell’elemento nella lista.
Esempio
enumerate [’a’;’b’;’c’];;
- : (char * int) list = [(’a’, 0); (’b’, 1); (’c’, 2)]
Liste
5/15
Enumerazione di insiemi - Soluzione
l e t enumerate l =
l e t r e c aux c = f u n c t i o n
[ ] −> [ ]
| x : : x s −> ( x , c ) : : aux ( c +1) x s
i n aux 0 l ; ;
Liste
6/15
Liste strettamente crescenti
Costruire una funzione increasing : ’a list -> ’a list
che preso in input una lista di elementi restituisca la lista che
rimuove elementi se non sono in ordine crescente
Esempio
increasing [2;5;3;8;1;2;3];;
- : int list = [2; 5; 8]
Liste
7/15
Liste strettamente crescenti
Costruire una funzione increasing : ’a list -> ’a list
che preso in input una lista di elementi restituisca la lista che
rimuove elementi se non sono in ordine crescente
Esempio
increasing [2;5;3;8;1;2;3];;
- : int list = [2; 5; 8]
Suggerimento 1. Si pu`
o pensare di tenere traccia del massimo
elemento letto fino a quel punto in una funzione interna.
Liste
7/15
Liste strettamente crescenti - Soluzione
let increasing = function
[ ] −> [ ]
| x : : x s −>
l e t r e c aux max = f u n c t i o n
[ ] −> [ ]
| x : : x s −>
i f x > max t h e n
x : : ( aux x x s )
else
aux max x s
i n x : : ( aux x x s ) ; ;
Liste
8/15
La funzione map
La funzione map `e una funzione di ordine superiore che presa in
input una lista e una funzione generica applica la funzione ad ogni
elemento della lista. La sua firma `e map: (’a -> ’b) -> ’a
list -> ’b list
l e t r e c map f = f u n c t i o n
[ ] −> [ ]
| x : : x s −> ( f x ) : : map f x s ; ;
Liste
9/15
La funzione filter
Costruire una funzione che “filtri” una lista usando la funzione
booleana f in ingresso, ossia che se f `e vera aggiunge l’elemento
alla lista altrimenti no
Liste
10/15
La funzione filter
Costruire una funzione che “filtri” una lista usando la funzione
booleana f in ingresso, ossia che se f `e vera aggiunge l’elemento
alla lista altrimenti no
Suggerimento 1. La funzione filter non `e molto diversa da map,
solo che se f applicata ad un argomento `e verificata si concatener`a
l’elemento alla lista, altrimenti si richiamer`a la funzione filter sulla
sottolista.
Liste
10/15
La funzione filter - Soluzione
l e t rec f i l t e r f = f u n c t i o n
[ ] −> [ ]
| x : : x s −>
i f ( f x ) then x : : ( f i l t e r f xs )
e l s e ( f i l t e r f xs ) ; ;
Liste
11/15
La funzione filter - Soluzione
l e t rec f i l t e r f = f u n c t i o n
[ ] −> [ ]
| x : : x s −>
i f ( f x ) then x : : ( f i l t e r f xs )
e l s e ( f i l t e r f xs ) ; ;
E se volessimo costruire una funzione che preso in input una lista
di interi restituisca la lista con i soli numeri pari?
Liste
11/15
La funzione filter - Soluzione
l e t rec f i l t e r f = f u n c t i o n
[ ] −> [ ]
| x : : x s −>
i f ( f x ) then x : : ( f i l t e r f xs )
e l s e ( f i l t e r f xs ) ; ;
E se volessimo costruire una funzione che preso in input una lista
di interi restituisca la lista con i soli numeri pari?
Soluzione. let only even lst = filter (fun x -> x mod 2
= 0) lst;;
Liste
11/15
Insieme delle parti
Costruire una funzione che calcoli l’insieme delle parti, ossia che
dato in input una lista restitusca la lista di tutte le possibili
sottoliste.
e.g. powerset [1;2] = [[]; [1]; [2]; [1;2]]
Liste
12/15
Insieme delle parti
Costruire una funzione che calcoli l’insieme delle parti, ossia che
dato in input una lista restitusca la lista di tutte le possibili
sottoliste.
e.g. powerset [1;2] = [[]; [1]; [2]; [1;2]]
Hint 1. L’insieme delle parti ha una definizione ricorsiva in quanto
lo si pu`o pensare come caso base restituisca una lista di liste vuote
(i.e. [[]]) e nel caso ricorsivo come la concatenazione (operatore @)
dell’insieme delle parti ottenuto rimuovendo un elemento e la lista
di sottoinsiemi ottenuti aggiungendo l’elemento rimosso ad essi
Liste
12/15
Insieme delle parti
Costruire una funzione che calcoli l’insieme delle parti, ossia che
dato in input una lista restitusca la lista di tutte le possibili
sottoliste.
e.g. powerset [1;2] = [[]; [1]; [2]; [1;2]]
Hint 1. L’insieme delle parti ha una definizione ricorsiva in quanto
lo si pu`o pensare come caso base restituisca una lista di liste vuote
(i.e. [[]]) e nel caso ricorsivo come la concatenazione (operatore @)
dell’insieme delle parti ottenuto rimuovendo un elemento e la lista
di sottoinsiemi ottenuti aggiungendo l’elemento rimosso ad essi
Hint 2. Si pu`o usare la funzione map per aggiungere ad ogni
sottolista un elemento, usando la funzione fun l -> x::l
Liste
12/15
Insieme delle parti - Soluzione
l e t rec powerset = f u n c t i o n
[ ] −> [ [ ] ]
| x : : x s −>
l e t sub = p o w e r s e t x s i n
sub @ ( map ( f u n l −> x : : l ) sub ) ; ;
Liste
13/15
Sottoinsiemi di cardinalit`a almeno n
Costruire una funzione che rimuova le liste di cardinalit`a < n dalla
dalla liste di tutte le sottoliste
Liste
14/15
Sottoinsiemi di cardinalit`a almeno n
Costruire una funzione che rimuova le liste di cardinalit`a < n dalla
dalla liste di tutte le sottoliste
Hint 1.Usare le funzioni filter e length
Liste
14/15
Sottoinsiemi di cardinalit`a almeno n - Soluzione
l e t r e c remove n l s t =
f i l t e r ( f u n l −> ( l e n g t h l ) > n ) ( p o w e r s e t l s t ) ; ;
Liste
15/15

Download Report