1,2. Lunedì 17 marzo
Introduzione al linguaggio ML: dichiarazioni, scope, tipi base, funzioni ricorsive.
Esercitazione. Esercizi sul principio di Induzione: dimostrazione del principio di
induzione completa.
3. Mercoledì 19 marzo
ML: coppie, record, pattern matching.
Call-by-value, funzioni di più argomenti e currificazione.
Funzioni di ordine superiore e polimorfismo: monotipi e politipi.
Esempi
4. Mercoledì 26 marzo
Funzionali sulle liste: map, reduce, zip.
Loro applicazioni al prodotto scalare tra vettori.
Confronto con l'usuale programma iterativo
Funzioni anonime con notazione à la lambda calcolo: "fn x => ...".
La funzione powerset.
Esercizi Assegnati [1]:
1. Scrivere una funzione che traspone una matrice, rappresentata come lista di liste.
2. Rappresentando un insieme come una lista, scrivere una funzione che presi in input
un insieme S ed un naturale n, restituisce tutti i sottoinsiemi di S di cardinalita' n.
Liste
Vettori&Matrici
Soluzioni
5. Mercoledì 2 aprile
Tipici programmi sulle liste: reverse, elimCopie, merge.
L'algoritmo mergesort in ML.
Tipi di dato definiti dall'utente.
Esercizi Assegnati [2]:
1. Scrivere una funzione quicksort che ordina una lista.
La funzione dovrebbe avere tipo: 'a list -> ('a -> 'a -> bool) -> 'a list.
in quanto parametrizzata rispetto alla relazione secondo la quale si ordina la lista.
2. Scrivere una funzione che fa il prodotto tra matrici.
Definizioni di Tipi di Dato
Soluzioni
6. Mercoledì 9 aprile
Correzioni esercizi [1] e [2].
Tipi definiti dall'utente: nat, mylist, bintree. Tipi e funzioni
mutuamente ricorsivi: ntree.
Esercizi Assegnati [3]:
1. Scrivere una funzione selectSort e insertSort per ordinare una lista.
2. Date due liste P ed I che rappresentano rispettivamente una visita preorder
ed in order
dello stesso albero binario, sotto quali condizioni e' possibile ricostruire in modo UNIVOCO l'albero di
partenza?
Ossia esiste UN SOLO albero che ha quelle visite preorder e inorder.
3. Scrivere una funzione ML che prese in ingresso due liste
(della stessa lunghezza)
restituisce UN albero che ha la prima lista come visita preorder e la seconda come visita inorder.
Alberi
Soluzioni
7,8. Lunedì 14 aprile
Definizione di tipi astratti: vantaggi e limiti.
Il sistema dei moduli di ML.
Cenni a elementi non funzionali di ML: referenze ed eccezioni.
9. Mercoledì 30 aprile
Introduzione al linguaggio LISP.
Atomi e Liste. Funzioni base: setq, car, cdr, cons, ...
Struttura e valutazione di un'espressione LISP.
Controllo esplicito della valutazione: il quote.
Esercizi Assegnati [4]:
Scrivere in ML la funzione map senza decomporre la lista di
ingresso. [Sugg: usare il funzionale reduce]
Atomi, Liste, Quote, ...
Soluzioni
10. Mercoledì 7 maggio
Discussione soluzioni Esercizi [3] e [4].
Ancora sul Lisp: definizioni di funzioni.
Esercizi Assegnati [5]:
1. Scrivere in LISP una funzione che valuta un espressione
definita dalla sintassi:
Expr ::= (Expr op Expr) | num
op ::= piu | meno | per | div
2. Considerare espressioni con variabili, da valutare con un
ambiente di valutazione
rappresentato con una lista di
coppie (variabile valore).
11. Mercoledì 12 maggio
Correzione Esercizio [5].
Primitive non funzionali del LISP: rplaca, rplacd, setf.
Funzioni con piu' di un body. LET.
Esercizi Assegnati [6]:
Arricchire il linguaggio delle espressioni con un
costrutto nella forma:
(LETVAL ((var exp) ... (var exp) exp)
Riflettere sull'interpretazione di un linguaggio arricchito
con:
(LETFUN (funName (parList) body) Exp)
e applicazione di funzione.
Riflettere sulle varie semantiche (lazy/eager, static/dynamic).
12. Mercoledì 19 maggio
Discussione Esercizio [6].
Presentazione dei Progetti (Terzo Esonero).
Progetto (.pdf)
13. Mercoledì 26 maggio
Discussione progetto.
14,15. Giovedì 27 maggio
Espressività della lazy evaluation.
Presentazione delle letture consigliate sui linguaggi
funzionali.
Aggiornata il 12/5/2003 da Ivano Salvo