ESERCIZI SCHEME
Esercizio 1
La seguente espressione Scheme contiene due errori di sintassi.
Quali?
(define pippo (lambda (x) (x + 3) )
Esercizio 1.5
Qual e' il valore di un'espressione define in Scheme?
Esercizio 2
Definire una funzione Scheme ricorsiva che prenda in input un
numero naturale n e calcoli la somma di tutti i numeri pari da 0 a n.
(Il predicato Scheme che controlla se un numero e' pari e' even? )
Esercizio 3
Definire in Scheme la funzione "Manoh" che, preso un numero n,
restituisce la somma dei quadrati dei naturali da 0 ad n.
Esercizio 4
Definire in Scheme la funzione "Mavah" che, preso un numero n,
restituisce il quadrato della somma dei naturali da 0 ad n.
Esercizio 5
Definire in Scheme la funzione "Madaih" che, preso un numero n,
restituisce la somma dei naturali da 0 ad n.
Esercizio 6
Definire in Scheme la funzione "Masih" che, preso un numero n,
restituisce il quadrato della somma dei naturali da 0 ad n.
Esercizio 6.5
Supponiamo di aver definito in Scheme una funzione a valori booleani (un predicato) "cucu?".
Definire una funzione Scheme che, dati in input due numeri naturali n ed m (n<=m), restituisca la somma di tutti i numeri compresi tra n ed m che soddisfano il predicato "cucu?".
Esercizio 7
Fornire una funzione Scheme che, preso in input un predicato P?
sui naturali restituisca una funzione sui naturali che vale 2 sui
numeri su cui P? e' vero e 3 sui numeri su cui
P? e' falso.
Esercizio 7.5
Definire una funzione Scheme che, presi in input
due funzioni f e g sui naturali e un predicato P?
sui naturali, restituisca una funzione che vale
come f sui valori per cui vale P? e come g su
quelli per cui P? non vale.
Esercizio 8
Dire perche' in SCHEME non e' possibile utilizzare le codifiche
dei tipi base come fatto nel lambda calcolo. Per esempio non e'
possibile utilizzare \xy.x e \xy.y per codificare #t e #f.
Una possibile soluzione.
Esercizio 9
-
Si definisca in SCHEME una funzione both che, preso un predicato unario P, restituisca un
predicato binario che e' vero se e solo se su entrambi i suoi argomenti vale P.
Dimostrare per induzione che la funzione both definita e' totale.
-
Definire in SCHEME la funzione compose che, prese due funzioni ne restituisce la loro
composizione.
-
Definire in SCHEME la funzione neither che, preso un predicato unario P, restituisca un
predicato binario che e' vero se e solo se su entrambi i suoi argomenti P non vale.
Tale funzione deve essere definita utilizzando both e compose.
Una possibile soluzione.
Esercizio 9.5
Elencare tutto gli errora presenti nel seguente programma scheme
(define ((funzion n)
(if (n=0)
then (1)
else (+ (funzion (- n 1)) (funzion (- n 1)))))
Quale funzione matematica sui naturali calcolerebbe "funzion" se non ci fossero errori?
Esercizio 9.7
Quale funzione matematica sui numeri naturali e' calcolata dalla seguente funzione Scheme?
(define (f n)
(if (or (= n 0) (= n 1))
0
(+ 1 (f (- n 2)))))
Esercizio 9.8
Cosa calcola la seguente funzione?
(define (X f)
(if (= (f 0) 0)
0
(+ 1 (X (lambda (n) (f (+ n 1)))))))
Esercizio 9.9
Definire una funzione Scheme di ordine superiore,
divisibileper, che preso un naturale p, restituisca
il predicato che controlla se un naturale sia divisibile per p.
(Si puo' utilizzare la funzione predefinita modulo che
restituisce il resto della divisione intera)
Esercizio 10
Dire cosa fa la seguente funzione SCHEME "guess".
Si assuma che l'unico tipo base a disposizione siano numeri.
(define (guess what is)
(if (null? is)
'()
(cons (cond
( (not (number? (car is))) (guess what (car is)) )
( (what (car is)) 0 )
( else (car is) ) )
(guess what (cdr is)) ) ) )
e dimostrare formalmente che "guess" fa esattamente
quanto si e' affermato.
Una possibile soluzione.
Esercizio 11
Definire le funzioni SCHEME (max n m) e (half n) dove n ed m sono numeri naturali.
La prima restituisce il massimo tra n ed m, mentre la seconda l'arrotondamento di n/2
al naturale inferiore.
Le due funzioni devono venir definite per ricorsione. L'unico predicato su numeri
utilizzabile e' l'uguaglianza. Le uniche funzioni numeriche utilizzabili sono le due seguenti:
(define (inc n) (+ n 1))
(define (dec n) (- n 1))
Una possibile soluzione.
Esercizio 12
Considerate le seguenti funzioni SCHEME, dove l'argomento P? e' da considerarsi
sempre un predicato su naturali:
(define (min P? b)
(define (aux n)
(cond ((and (P? n) b) n)
((and (not (P? n)) (not b)) n)
(else (aux (+ n 1)))))
(aux 0))
(define (F P?)
(if (<= (min P? #t) 10)
(lambda (x) (if (< x (min P? #t))
#f
(P? x)))
(F (lambda (x) (if (= x (- (min P? #t) 1))
#t
(P? x))))))
Cosa fa min?
Quale sottoespressione propria (cioe' non tutto il body della funzione)
nella definizione di F si puo'
sostituire con "P?" in modo che F continui a fare quello che fa, ma la sua definizione
risulti piu' semplice?
Cosa fa F?
Dire su quale insieme di argomenti "P?" la valutazione di (min P? b) converge.
Dimostrare
che sul dominio dei predicati veri almeno in un punto (F P?) e' totale.
Fornire una versione di F che non utilizzi la ricorsione.
Ad occhio, secondo voi si potrebbe dare una versione di min che non utilizzi
una funzione ausiliaria con ricorsione di coda? Sempre ad occhio, perche'?
Una possibile soluzione.
Esercizio 13
Dire cosa fanno le seguenti funzioni fstt e changefst
(define (fstt P)
(letrec ((aux (lambda (P n)
(if (P n)
n
(aux P (+ n 1))))))
(aux P 0)))
(define (changefst P)
(lambda (x) (if (= (fstt P) 0)
(P x)
(= x (- (fstt P) 1)))))
Dare un esempio di argomento su cui fstt converga e su cui invece diverga.
Su quale dominio la funzione fstt risulta totale?
Una possibile soluzione.
Esercizio 14
Consideriamo la classe di funzionali F con il seguente comportamento
F: (Int -> Int) -> (Int -> Int) -> ...... (Int -> Int) -> Int
\_____________________ n-volte __________________/
(ogni funzionale puo' avere un n differente ed e' praticamente
la versione currificata di una funzione di n argomenti che sono funzioni da
numeri a numeri e che restituisce numeri)
Scrivere una funzione Scheme Donald che presa una funzione F della classe
sopra descritta, restituisca il valore di n.
ESEMPIO: (Donald (lambda (f) (lambda (g) (+ (g 3) (f 3)))) ) -----> 2
Se si vuole si puo' utilizzare il predicato predefinito "number?".
Una possibile soluzione.
Esercizio 15
Definire un funzionale Scheme Miciomiao che, presa in input una funzione f da
interi ad interi restituisca una funzione che vale come f sui valori dispari
e il doppio di f sui valori pari.
Una possibile soluzione.
Esercizio 16
Definire una funzione Scheme Miciomiao che, prese in input due funzioni f e g da
interi ad interi restituisca una funzione che vale come f sui valori dispari
e come g sui valori pari.
Esercizio 17
Si consideri la seguente funzione Scheme
(define (Cur f n)
(if (= 0 n)
f
(lambda (x) ((Cur f (- n 1)) x))))
Cur prende in input una funzione f, l'arita' n di tale funzione
(il numero dei suoi argomenti) e restituisce la versione curryficata di f.
La funzione Cur rispetta la specifica appena data?
se si, dimostrare che e' totale.
se no, fare un semplice esempio che ne dimostri il perche'.
Una possibile soluzione.
Esercizio 18
Definire una funzione Scheme che, data una lista,
restituisca una lista formata dagli elementi della lista in input in
posizione pari.
Una possibile soluzione.
Esercizio 18.5
Supponiamo di non avere in Scheme il tipo di dato predefinito dei
numeri naturali.
Lo definiamo allora nel seguente modo, utilizzando
delle liste per la rappresentazione dei numeri naturali.
(define zero '( ) )
(define succ (lambda (n) (list n)))
(define iszero? null?)
(define pred ....)
Dire cosa inserire al posto dei puntini per definire correttamente il selettore pred.
Utilizzando il tipo appena definito, fornire la funzione Scheme che somma due numeri naturali.
Definire anche il predicato ugual?, che confronta due numeri naturali, il
predicato maggior? e la funzione max, dall'ovvio significato.
Esercizio 19
Scrivere un' espressione Scheme che corrisponda alla lista
infinita di 0. (Non bisogna usare il define e non
importa che la valutazione di tale espressione porti ad una valutazione
infinita)
Esercizio 19.5
Definire una funzione Scheme che, presa in input una lista
di numeri, restituisca la lista di quegli elementi tali che
la somma con il successivo sia minore stretto di 7.
Es. (3 2 6 5 1 3) ---> (3 5 1 3)
Esercizio 20
Cosa calcola la seguente funzione SCHEME?
(define (X? y?)
(lambda (x)
(or (null? x)
(and (list? x)
(y? (car x))
((X? y?) (cdr x))))))
Una possibile soluzione.
Esercizio 21
E' possibile scrivere un'espressione SCHEME che rappresenti una lista infinita di elementi?
Se si, dire brevemente come si puo' fare e se poi e' possibile utilizzare tale espressione
per fare delle computazioni.
Se no, dire perche' e cosa andrebbe cambiato dello SCHEME perche' la cosa diventi possibile
e se il cambiamento proposto permetterebbe di utilizzare un'espressione del genere
per fare delle computazioni.
Una possibile Soluzione.
Esercizio 22
Definire una funzione SCHEME che prenda in input una lista ls di numeri
e produca la lista delle somme degli elementi di tutti i possibili
sottinsiemi (escluso quello vuoto) dell'insieme degli elementi di ls.
Esempio:
(F (2 4 1)) ---> (2 4 1 5 3 6 7)
(F (5 7)) ---> (5 7 12)
(F (1 1 2)) ---> (1 1 2 3 2 3 4)
Una possibile soluzione.
Esercizio 23
Una lista gallega e' una lista di numeri in cui tutti i numeri pari sono
messi in ordine decrescente, mentre i dispari sono in ordine crescente.
Es. (8 5 9 6 13 2) e' gallega, mentre (8 5 3 6 13 2) e (8 5 9 10 13 2) non lo sono.
Scrivere una funzione SCHEME, gaita, che, preso un numero n ed una lista gallega ls,
``inserisca'' n in ls nella posizione che sia piu' a sinistra possibile, ma tale che
la lista ottenuta risulti ancora gallega.
Es. (gaita 7 (8 5 6 2) ) --> (8 5 7 6 2)
(gaita 4 (8 5 6 2 9 15) ) --> (8 5 6 4 2 9 15)
Una possibile soluzione.
Esercizio 24
Definire una funzione Scheme (un predicato, per essere piu'
precisi) "alternevenodd?" su liste di numeri naturali, che restituisca vero se e
solo se ogni numero pari della lista di input (tranne eventualmente l'ultimo,
ovviamente) e' seguito da un numero dispari e viceversa. Ovviamente e' possibile
utilizzare i predicati even? e odd? di Scheme.
Esempio: (alternevenodd? (list 3 6 7 8 1 4)) ---> #t
(alternevenodd? (list 6 2 7 4 3)) ---> #f
Possibili soluzioni (anche by Sergio Di Mare).
Esercizio 25
Cosa calcola la seguente funzione Scheme?
(define (X y? n)
(lambda (x)
(or (and (null? x) (= n 0))
(and (not (null? x))
(if (y? (car x)) ((X y? (- n 1)) (cdr x)) ((X y? n) (cdr x)) )))))
Dimostrare che la valutazione di (X y? n) termina per ogni y? e per ogni n.
Dimostrare che la valutazione di ((X even? n) ls) termina per ogni naturale n e lista ls.
Una possibile soluzione.
Esercizio 26
Definire una funzione che prenda in input una lista ls di numeri e tre numeri
n1, n2 e n3 tali che n1 < n2 < n3.
La funzione dovra' restituire una lista di tre liste tali che gli elementi della
prima sono tutti gli elementi di ls strettamente minori di n1, gli elementi
della seconda sono tutti gli elementi di ls compresi tra n1 e n2 e gli elementi
della terza sono tutti gli elementi di ls strettamente maggiori di n3.
Non definire la funzione utilizzando funzioni ausiliarie.
Una possibile soluzione.
Esercizio 27
Definire una funzione che prenda una lista e un predicato di ordinamento totale e restituisca
la lista ordinata secondo tale predicato utilizzando l'algoritmo del quicksort.
Una possibile soluzione.
Esercizio 28
Definire una funzione che prenda una lista e un predicato di ordinamento totale e
restituisca
la lista ordinata secondo tale predicato utilizzando l'algoritmo del Mergesort.
Una possibile soluzione.
Esercizio 29
Definire una funzione SCHEME che prenda in input una lista ls di numeri ed un num
ero n.
La funzione dovra' restituire una lista di due liste tali che gli elementi della
prima siano tutti gli elementi di ls strettamente minori di n (nello stesso ordin
e in cui
si trovano in ls) e gli elementi
della seconda siano tutti gli elementi di ls maggiori o uguali a n (nello stesso
ordine
in cui si trovano in ls).
Non utilizzare, se potete, funzioni ausiliarie.
Cercare di usare l'espressione let e dire qual'e' il vantaggio del suo eventuale
utilizzo.
Una possibile soluzione.
Esercizio 30
Definire la funzione Scheme MaxLiv che,
presa una lista contenente numeri o liste a qualsiasi livello di
annidamento, restituisca il maggior livello di annidamento.
Es.: MaxLiv di (9 ( (4 5) (7 '())) )
e' 3
Esercizio 30.5
Cosa calcola la funzione G, supponendo che il suo
argomento sia una funzione dai naturali ai naturali?
(define (G f) (F f 0))
dove F e' definita nel modo seguente
(define (F f n)
(if (= (f n) 0)
0
(+ 1 (F f (+ n 1)))))
Qual e' il valore della seguente espressione?
(G (lambda (n) (if (= n 4) 0 (+ n 1))) )
Esercizio 31
Definire una funzione SCHEME:
INPUT: una lista ls di numeri, una lista di funzioni numeriche unarie lsf, un predicato su
funzioni numeriche unarie PF e un funzionale da funzioni unarie a funzioni
unarie G (una funzione che prende una funzione unaria
e restituisce una funzione unaria), tali che lunghezza(ls) = lunghezza(lsf).
OUTPUT: una lista ls' di numeri
SPECIFICA: lunghezza(ls) = lunghezza(ls'). Inoltre, se con i-esimo(l) indichiamo
l'i-esimo elemento di elemento di una lista l, allora
i-esimo(ls') = i-esimo(lsf)(i-esimo(ls)) se vale PF(i-esimo(lsf)), G(i-esimo)(lsf))(i-esimo(ls)) altrimenti.
Una possibile soluzione.
Esercizio 32
Definire una funzione SCHEME F che prenda in input un predicato unario su numeri ed una lista i cui elementi sono
numeri o liste annidate (a qualsiasi livello) di numeri e restituisca una lista uguale a quella di input, ma in cui
ci sia 0 al
posto di tutti quei numeri che soddisfano il predicato.
Esempio: F( (lambda (x) (> x 7)) , ((2 (3 () 9)) 1 (((8)))) ) = ((2 (3 () 0)) 1 (((0))))
Una possibile soluzione.
Esercizio 33
Definire in SCHEME una funzione "pam" che prenda come argomento una lista ls di
funzionali, una funzione f da naturali a naturali ed un numero k.
(Si assume che i funzionali in ls prendono funzioni unarie da naturali in naturali
e restituiscono funzioni dello stesso tipo).
Il valore restituito sara' il valore ottenuto applicando la funzione f a tutti i funzionali
in ls ed applicando k alla composizione di tutte le funzioni cosi' ottenute.
Intuitivamente: (pam (F1 F2 F3) f k ) ---> F1(f)(F2(f)(F3(f)(k)))
Una possibile soluzione.
Esercizio 34
Definire una funzione che prenda una lista ls composta di un numero di elementi pari
a 2^k (2 alla kappa) con k numero naturale e
restituisca una lista di liste descritta dal seguente esempio:
input: (a b c d e f g h i l m n o p q r)
output: (((((a) (b)) ((c) (d))) (((e) (f)) ((g) (h)))) ((((i) (l)) ((m) (n))) (((o) (p)) ((q) (r))))).
Ovviamente non si puo' dare la specifica di una funzione con un esempio!!! quindi, dopo aver
scritto la funzione in scheme, descriverne anche la specifica in modo formale.
Una possibile soluzione.
Una possibile soluzione.
Esercizio 35
Risolvere l'esercizio precedente utilizzando ricorsione di coda, ed in particolare
facendo il modo che l'output della funzione venga prodotto "iterando"
sull'input la funzione che, presa una lista con 2n elementi,
restituisca una lista di liste in cui gli elementi sono raggruppati due a due.
Una possibile soluzione.
Esercizio 36
Scrivere una funzione SCHEME che, presa una lista di numeri naturali, restituisca
la somma dei numeri dispari presenti nella lista e che utilizzi ricorsione di coda.
(Si puo' supporre di avere a disposizione il predicato "odd?" che e' vero sui numeri dispari)
Brevemente, e' possibile definire la funzione "substitute" del punto (a) per ricorsione di coda?
Se si, sarebbe comunque non semplice? perche'? Se no, perche'?
Una possibile soluzione.
Esercizio 37
Definire la funzione SCHEME appGen che, presa una lista di liste di naturali, restituisca
la loro concatenazione.
Definire appGen preferibilmente senza utilizzare la funzione append.
Fornirne una versione che utilizza ricorsione di coda (in tale versione si puo'
utilizzare la funzione append).
Una possibile soluzione.
Esercizio 37.5
Qual e' la relazione di precedenza indotta dalla seguente
funzione Scheme sui naturali?
(define (F n)
(if ((divisibileper 7) n)
(* n 5)
(* (F (- n 1)) 3)))
Esercizio 38
Dire cosa fa la seguente funzione SCHEME "guess".
Si assuma che l'unico tipo base a disposizione siano numeri e che le liste che
si considerano non abbiano liste vuote come elementi.
(define (guess what is)
(if (null? is)
'()
(cons (cond
((not (number? (car is))) (guess what (car is)) )
( else (car is) ) )
(guess what (cdr is)) ) ) )
Dimostrare formalmente che "guess" e' totale.
Una possibile soluzione.
Esercizio 39
Dire cosa fa la seguente funzione SCHEME "guess".
Si assuma che l'unico tipo base a disposizione siano numeri e che nessuna lista
possa contenere la lista vuota come elemento.
(define (guess what is)
(cond
((null? is) '())
( what (guess what (cdr is)))
((not (number? (car is))) (cons (guess what (car is) ) (guess what (cdr is)) ))
(else (cons (car is) (guess what (cdr is))))))
dimostrare formalmente che "guess" fa quanto dichiarato.
Una possibile soluzione.
Esercizio 40
Definire una funzione (un predicato in realta') che prenda una lista e un predicato e
restituisca #t se e solo se tutti gli elementi della lista soddisfano il predicato.
Una possibile soluzione.
Esercizio 41
Scrivere una funzione Scheme che, presa una lista con livello
arbitrario di annidamento, restituisca il numero di liste che essa
contiene.
Esercizio 42
(a) Si condideri la seguente definizione informale del tipo di dato
Sarchiapone :
Un sarchiapone e' o il manzanillo o il
minollo, oppure eŽ il tirulero di un numero naturale e di un
sarchiapone, oppure eŽ il zumpappero di due sarchiaponi e di una
lista di numeri naturali.
Definire in Scheme il tipo di dato Sarchiapone .
Scrivere in Scheme la funzione porompoppo che, preso un sarchiapone S e due
numeri naturali n e m, ritorna un sarchiapone uguale ad S, ma con tutte le
possibili occorrenze del numero n nel sarchiapone sostituite con m.
(b) Definire in HASKELL il tipo di dato Sarchiapone di cui
al punto precedente
Una possibile soluzione.
Esercizio 43
Scrivere una funzione Scheme su liste (o su alberi, se si vuole) e
la cui totalita' si dimostri in modo abbastanza naturale utilizzando
una relazione di precedenza di tipo lessicografico.
(Non importa cosa faccia la funzione che definite).
Una possibile soluzione.
Esercizio 44
Si definisca in Scheme il tipo di dato Albero Binario con
Etichette Numeriche e si definisca una funzione che prende in input un
albero binario ed una lista composta da elementi che possono essere 0 o
1. La funzione restituisce in output l'etichetta del nodo identificato
dalla lista (si scende, a partire dalla radice, a sinistra se c'e' uno
0, e a destra se c'e' 1)
Esercizio 44.5
Un piriponzio e' il cucu o il settete, oppure si ottiene sfrunziando
due piriponzi con un numero naturale.
Supponiate di aver definito in Scheme il tipo di dato piriponzio.
Definire una funzione Scheme che, preso un piriponzio,
ci dice quante volte e' stato utilizzato il cucu per la sua formazione.
Esercizio 45
Definire una funzione che, preso in input un albero binario con
etichette numeriche
ed un numero n, restituisca la lista che identifica il percorso che
sull'albero identifica
un percorso dalla radice alla foglia con etichetta n, e che restituisca
la lista vuota se
n non e' presente nell'albero. Il percorso e' una lista composta da 0
(vai a sinistra), 1 (vai a destra)
e sempre terminante con 2.
Esempio: la funzione
su
3
e
5
restituisce (1 2)
/ \
6 5
/
1
Una possibile soluzione.
Esercizio 46
Negli appunti delle lezioni e' definito un predicato di ordinamento parziale
tra alberi (T1 >> T2 sse [T2 e' ottenuto da T1 eliminando "un pezzo in basso a sinistra").
Negli appunti tale ordinamento in realta' e' tra rappresentazioni di
alberi come liste di liste.
Definire il tipo di dato astratto Albero Etichettato con etichette numeriche
e con nodi con numero arbitrario di figli. (Visto che a lezione non abbiamo visto
come trattare il caso di funzioni che prendono un mumero arbitrario di argomenti,
si puo' pensare di dare al costruttore di alberi una lista di sottoalberi)
Definire il predicato >> tra alberi, ma questa volta tra alberi veri,
non operando cioe' sulla loro rappresentazione interna, ma lavorando
esclusivamente con gli operatori primitivi sugli alberi (costruttori, selettori,
predicati).
Modificare la definizione del tipo di dato precedente in modo da avere
etichette di un qualsiasi altro tipo. (c'e' bisogno di fare qualcosa?)
Una possibile soluzione (?) . (By E. Erba)
Esercizio 47
Definire una funzione SCHEME che, preso un Albero Etichettato con etichette
di tipo arbitrario ed un predicato di ordinamento totale sugli elementi
del tipo delle etichette, restituisca un albero in cui i
i figli di ogni nodo risultino ordinati secondo il predicato dato.
Una possibile soluzione (?). (By E. Erba)
Esercizio 48
Scrivere in SCHEME un predicato su elementi del tipo di dato astratto
Albero Binario che controlli se un albero binario e' completamente bilanciato
(un albero binario e' completamente bilanciato
se il numero dei suoi nodi e' 2n-1, dove n e' la sua profondita'
[l'albero con un solo nodo ha profondita' 1]).
Una possibile soluzione.
Esercizio 49
Definire il tipo di dato astratto "albero binario di ricerca etichettato e non bilanciato" di numeri interi.
Definire le funzioni di inserimento nell' albero e visita inorder, preorder e postorder.
Una possibile soluzione.
Esercizio 50
Definire il tipo di dato astratto "Albero binario con etichette numeriche positive".
Un nodo di un albero binario puo' essere identificato da una lista di "0" e "1".
Definire una funzione SCHEME G che, preso un albero del tipo definito, restituisca una funzione
da liste di "0" e "1" a numeri interi tale che (G ls) = n se n e' l'etichetta del nodo identificato
dalla lista ls o il valore -1 se ls non identifica alcun nodo. (La lista vuota identifica la radice
di un albero).
Una possibile soluzione.
Esercizio 51
Definire in SCHEME il tipo di dato astratto Albero Binario NON etichettato.
Definirlo anche in Haskell.
Esercizio 52
Definire il tipo di dato astratto "Albero binario con etichette numeriche solo sulle foglie".
Considerando che un nodo di un albero binario puo' essere identificato da una lista di "0" e "1",
definire una a scelta (facoltativamente entrambe) delle seguenti funzioni:
Una funzione SCHEME che, preso un albero del tipo descritto restituisca la lista delle sue foglie
da destra a sinistra (nella definizione della funzione non bisogna usare la funzione reverse su liste).
Una funzione SCHEME che,
preso un numero k ed una funzione f da {liste di "0" e "1" di lunghezza uguale a k} a {numeri naturali},
restituisca l'albero binario di profondita' k in cui la foglia identificata dalla lista ls
abbia f(ls) come etichetta. (Si assume che la profondita' di un albero di un solo nodo sia 0)
Una possibile soluzione.
Esercizio 53
Scrivere una funzione maxlabel SCHEME che, preso un albero binario
con etichette numeriche positive, restituisca l'etichetta di
valore massimo tra quelle dei suoi nodi.
Scriverne poi una versione che utilizzi ricorsione di coda
(una possibilita' e' utilizzare un parametro che rappresenti
un valore massimo temporaneo durante la scansione dell'albero
per livelli).
Una possibile soluzione.
Esercizio 54
Fornire una funzione SCHEME "zumpappa'" che prende in input un albero binario T,
un predicato P1, un predicato P2 ed un numero n.
L'albero binario T e' etichettato con etichette che sono funzioni unarie da naturali a
naturali. Il predicato P1 e' un predicato su funzioni unarie da naturali a naturali,
mentre il predicato P2 e' un predicato su naturali.
La funzione "zumpappa'" restituisce un albero simile a T, ma in cui se una funzione g
soddisfa il predicato P1 questa viene sostituita con una funzione che si comporta come
g, tranne che per i valori per in cui e' soddisfatto P2, nel qual caso il valore e' n.
Dimostrare che "zumpappa'" e' totale.
Una possibile soluzione.
Esercizio 55
Si supponga di avere il tipo di dato astratto albero binario etichettato, in cui le etichette
siano funzioni da naturali a naturali.
Definire una funzione SCHEME "parapaponzi" che prenda in input due alberi binari e restituisca
l'albero binario la cui struttura sia l'intersezione delle due strutture, e in cui le etichette
dei nodi siano la composizione delle etichette dei nodi corrispondenti negli alberi in input.
Esempio:
f w j
/ \ / \ / \
h g z r -----> l u
\ / \ / / /
s t v i k q
dove j e' la composizione delle funzione f e w, l e' la composizione delle funzioni h e z,
u quella delle funzioni g ed r, q la composizione di t e k.
Una possibile soluzione.
Esercizio 56
Definire una funzione SCHEME "ponzipo" che prenda in input una funzione f da naturali in naturali
e un numero naturale n,
e restituisca un albero binario completo (con funzioni da naturali a naturali come etichette)
tale che l'etichetta della radice sia
f, le etichette dei nodi a profondita' 1 siano funzioni uguali ad f tranne che su n valgono
f(n)-1, quelle al secondo livello, lo stesso, solo che su n valgono f(n)-2 e cosi' via.
Ovviamente se f(n)=0 allora ponzipo restituisce un albero formato da un solo nodo, con
etichetta f.
Esempio:
succ
/ \
(ponzipo succ 1) ----> succ' succ'
/ \ / \
succ" succ" succ" succ"
dove succ e' la funzione successore, succ' e' la funzione uguale a succ tranne che
succ'(1)=1, mentre succ" e' come succ tranne che succ"(1)=0.
Dimostrare che ponzipo e' totale.
Una possibile soluzione.
Esercizio 57
Supponiamo di aver definito il tipo di dato astratto Albero binario con etichette numeriche.
Scrivere una funzione SCHEME che preso un albero e un predicato restituisca la lista
di tutte le etichette dell'albero che soddisfano il predicato (l'ordine degli elementi nella
lista non e' rilevante).
Dimostrare che la funzione fornita rispetti la sua specifica.
Una possibile soluzione.
Esercizio 58
Scrivere una funzione SCHEME che prenda in input un elemento del
tipo di dato Albero binario con etichette numeriche non negative e la cui totalita'
si dimostri per induzione ben fondata utilizzando la seguente relazione
di precedenza:
Def.: tree1 << tree2 sse ( label(tree1) , altezza(tree1) ) < les ( (label(tree2) , altezza(tree2) )
Dove < les e' la relazione di precedenza lessicografica sulla coppia di relazioni di minore stretto
sui numeri naturali.
N.B.: Non importa cosa produca in output la funzione.
Una possibile soluzione.
Esercizio 59
Supponete di avere a disposizione il tipo di dato astratto
Albero Binario con nodi etichettati con numeri interi non negativi.
Dire cosa fa la funzione F definita sotto.
(define (X? tree)
(and (not (emptytree? tree))
(and (emptytree? (leftchild tree))
(emptytree? (rightchild tree)))))
(define (F tree)
(cond ((emptytree? tree) 0)
((X? tree) 1)
((not (= 0 (label tree))) (F (mktree (- (label tree) 1)
(leftchild tree)
(rightchild tree))))
(else (+ (F (leftchild tree)) (F (rightchild tree))))))
Dimostrare formalmente che F e' totale.
Dare poi una versione di F la cui totalita' sia dimostrabile per induzione
sull'altezza dell'albero dato in input.
Una possibile soluzione.
Esercizio 60
Definire una funzione Scheme che, preso un albero binario con
etichette numeriche ed un numero n restituisca il numero di etichette
uguali ad n.
Una possibile soluzione.
Esercizio 61
Supporre di avere il tipo di dato astratto Albero binario etichettato
con etichette numeriche.
Definire la funzione SCHEME che preso un albero restituisca la lista
di tutti i suoi sottoalberi (esclusi quelli vuoti).
Esempio:
(G 3 ) ---> ( 3 2 1 5)
/ \ / \ /
2 1 2 1 5
/ /
5 5
Una possibile soluzione.
Esercizio 62
Dimostrare per induzione ben fondata
che la seguente funzione SCHEME f, che prende in input un numero
naturale, una lista di numeri naturali e un albero binario etichettato con
etichette numeriche, e' totale.
(define (f n ls tree)
(cond ((and (= 0 n) (null? ls) (emptytree? tree))
(list 4 66))
((not (emptytree? tree))
(f n ls (childright tree)))
((not (= n 0))
(f (- n 1) (cons 4 (cons 66 ls)) (mktree 4 emptytree tree)))
((not (null? ls))
(f n (cdr ls) (mktree 66 tree tree)))))
Che cosa calcola f?
Una possibile soluzione.
Esercizio 63
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, Labelroot,
Rightchild, Leftchild.
Dire cosa calcola la seguente funzione Scheme e
dimostrarlo formalmente per induzione.
(define (guess what is)
(if (Emptytree? is)
Emptytree
(MKtree (if (not (= 0 (Labelroot is)))
(what (Labelroot is))
0 )
(guess what (Leftchild is))
(guess what (Rightchild is)))))
Esercizio 64
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, Labelroot,
Rightchild, Leftchild.
Dire cosa calcola la seguente funzione Scheme e
dimostrarlo formalmente per induzione.
(define (indovin che cos)
(if (Emptytree? cos)
(MKtree 0 Emptytree Emptytree)
(MKtree (che (Labelroot cos))
(indovin che (Leftchild cos))
(indovin che (Rightchild cos)))))
Esercizio 65
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, Labelroot,
Rightchild, Leftchild.
Dire cosa calcola la seguente funzione Scheme e
dimostrarlo formalmente per induzione.
(define (indovin che cos)
(if (Emptytree? cos)
Emptytree
(if (che (Labelroot cos))
Emptytree
(MKtree (Labelroot cos)
(indovin che (Leftchild cos))
(indovin che (Rightchild cos))))))
Esercizio 66
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, Labelroot,
Rightchild, Leftchild.
Dire cosa calcola la seguente funzione Scheme e
dimostrarlo formalmente per induzione.
(define (indovin che cos)
(if (Emptytree? cos)
Emptytree
(if (= 0 (che (Labelroot cos)))
Emptytree
(MKtree (che (Labelroot cos))
(indovin che (Leftchild cos))
(indovin che (Rightchild cos)))))
Esercizio 67
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, LabelRoot,
Rightchild, Leftchild.
Dire cosa fa la seguente funzione Scheme "indovin", supponendo che "un" appartenga
al dominio su cui fstt e' totale.
Dimostrare formalmente per induzione che "indovin" soddisfa la sua specifica.
(define (indovin un po)
(if (or (Emptytree? po) (= 0 (fstt un)))
Emptytree
(MKtree (Root po)
(indovin (changefst un) (Leftchild po))
(indovin (changefst un) (Rightchild po)))))
Esercizio 68
Si supponga di avere gia' definito il tipo di dato Albero Binario con Etichette Numeriche
e si consideri la seguente funzione SCHEME
(define (F bintree)
(define (aux bt par)
(cond ((Emptytree? bt) bt)
( par (MKtree 0
(aux (Leftchild bt) par)
(aux (Rightchild bt) par)))
((= 13 (LabelRoot bt)) (aux bt #t))
( else (MKtree (LabelRoot bt)
(aux (Leftchild bt) par)
(aux (Rightchild bt) par)))))
(aux bintree #f) )
F ha come argomento un albero binario con etichette numeriche,
mentre aux, che e' una funzione locale di F, ha come argomenti un albero binario con etichette numeriche e un booleano.
- Si dica cosa fa la funzione F (ovviamente cio' non significa mettere
in prosa il corpo della funzione);
- Si dica, giustificando la risposta, se la funzione ausiliaria aux e'
ricorsiva di coda;
- E' possibile dimostrare la totalita' di aux per induzione?
Se si, fornire una relazione di precedenza che permetta una tale dimostrazione.
Se no, giustificare perche' aux non si puo' dimostrare totale per induzione.
(Notare come a questa domanda sia possibile rispondere anche senza aver
risposto alle precedenti)
- Riscrivere F in modo piu' semplice, in modo da utilizzare anche piu'
funzioni, ma con un solo argomento.
Una possibile soluzione.
Esercizio 69
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con predicati su numeri:
Emptytree, MKtree, Emptytree?, LabelRoot,
Rightchild, Leftchild.
Definire una funzione Scheme patapunfete che preso un albero di questo
tipo, un numero n ed un valore booleano b,
restituisca una lista che contenga tutti i predicati presenti nell'albero
tali che il loro valore su n sia b.
Una possibile soluzione.
Esercizio 70
Si supponga di avere il tipo di dato Albero binario etichettato con etichette numeriche.
Si definisca la funzione Scheme che, preso un albero, un predicato P? su numeri, ed un
numero n,
restituisca un albero identico a quello in input, ma tale che le etichette che soddisfano P?
risultino sostituite con n.
Esercizio 71
- Definire una funzione Scheme che, presi due alberi binari
con etichette numeriche, rertituisca il numero di foglie che negli
alberi, in posizione uguale hanno etichetta uguale. Esempio:
4
7
/ \
/ \
3 8
3 9
--------------->
2
/
/ \ / \
1
4 5 1 8
Esercizio 72
Si supponga di aver definito in Scheme i costruttori, predicati e selettori
per il tipo di dato Albero Binario etichettato con etichette numeriche:
Emptytree, MKtree, Emptytree?, LabelRoot,
Rightchild, Leftchild.
Dire cosa calcola la seguente funzione Scheme e
dimostrarlo formalmente per induzione.
(define (indovin che cos)
(if (Emptytree? cos)
Emptytree
(if (che (LabelRoot cos))
Emptytree
(MKtree (LabelRoot cos)
(indovin (lambda (x) #t) (Leftchild cos))
(indovin che (Rightchild cos))))))
Una possibile soluzione.
Esercizio 73
Definire in SCHEME il tipo di dato astratto Albero Ternario con etichette numeriche non negative (la non negativita' servira' solo per dare una
particolare rappresentazione).
Definire inoltre una funzione
SCHEME che prenda in input un albero e restituisca il numero di etichette uguali a 0.
Una possibile soluzione.
Esercizio 74
Definire in Scheme i tipi di dato
Albero Ternario con Etichette Funzionali
(le etichette ai nodi di un albero di questo tipo sono funzioni da interi a interi)
Albero Ternario con Etichette Numeriche.
NB:E' sufficiente semplicemente indicare i costruttori, i selettori
e i predicati del tipo di dato. Non e' necessario implementarli.
Definire poi in SCHEME una funzione "revFtree" che prenda in input un albero del primo tipo
sopra definito ed un intero e restituisca in output un albero del secondo tipo.
L'albero in output avra' come struttura quella dell'albero in input "ribaltato" (ruotato di 180 gradi
sul suo asse centrale) e come etichette l'applicazione delle etichette al numero dato in input .
Esempio:
f f(n)
/ | | \
f' g n ----> g(n) f'(n)
/ \ | \ / | / \
g h' h f f(n) h(n) h'(n) g(n)
Dare uno schema di dimostrazione formale che la funzione Scheme definita
si comporta come specificato.
Esercizio 75
Definiamo nel seguente modo il tipo di dato astratto Albero Ternario con etichette numeriche non negative.
(define emptytree '() )
(define (emptytree? tree)
(null? tree) )
(define (mktree label tree1 tree2 tree3)
(list label tree1 tree2 tree3) )
(define (label tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(car tree) ) )
(define (childleft tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(cadr tree) ) )
(define (childcenter tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(caddr tree) ) )
(define (childright tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(cadddr tree) ) )
(a)
Definire in SCHEME il predicato binario "innertree?" definito su alberi
del tipo definito.
(innertree? T1 T2) e' vero sse T1 si puo' ottenere prendendo un sottoalbero
di T2 ed eliminando da questo alcuni suoi sottoalberi
(Per sottoalbero si intende tutto cio' che sta "sotto" ad un nodo).
Come esempio, definire due alberi tree1 e tree2 tali che
(innertree? tree1 tree2) sia vero.
(b)
Una lista di numeri dell'insieme {0,1,2} puo' identificare un nodo
di un albero del tipo sopra definito (la lista vuota rappresenta la radice,
la lista (0 2 1) rappresenta il nodo raggiungibile a partire dalla radice,
scendendo nel sottoalbero sinistro, poi andando ancora giu' per il sottoalbero
destro ed infine scendendo ancora al centro).
Definire in SCHEME un funzionale che prenda in ingresso una
funzione f unaria su numeri interi ed un albero del tipo definito,
e che restituisca una funzione che, presa una lista di
numeri dell'insieme {0,1,2}, restituisca il valore di f applicata
all'etichetta del nodo
identificato dalla lista. Si assuma per semplicita' che le liste fornite
alla funzione identifichino sempre un nodo e che l'albero fornito non sia mai
vuoto.
Fare poi un semplice esempio.
Aiutino: definire prima una funzione locale (o anche esterna, se si vuole)
che prenda un albero ed una lista del tipo definito e restituisca
l'etichetta del nodo identificato dalla lista.
Una possibile soluzione.
Una possibile soluzione.
Esercizio 76
Definire in SCHEME il predicato binario "embeddable?" definito su alberi del
tipo definito nell'esercizio precedente. (embeddable? T1 T2) e' vero sse
T1 e' un sottoinsieme di T2 (vedendo un albero come una relazione di
ordinamento parziale tra le sue etichette e vedendo una relazione, ovviamente,
come insieme di coppie).
Una possibile soluzione.
Esercizio 77
Prendiamo in considerazione il tipo di dato
il tipo di dato astratto Albero Ternario con etichette numeriche non negative
definito in uno degli esercizi precedenti.
(a)
Definire in SCHEME una funzione "revtree" che prenda un albero del tipo
sopra definito e restituisca l'albero "ribaltato" (ruotato di 180 gradi
sul suo asse centrale).
Esempio:
1 1
/ | | \
2 3 ----> 3 2
/ \ | \ / | / \
8 7 4 5 5 4 7 8
(b)
Come gia' detto in uno degli esercizi precedenti, un nodo di un albero del tipo visto sopra puo' essere identificato
da una lista di elementi dell'insieme {0,1,2} (intuitivamente,
0 indica "sinistra", 1 "centro" e 2 "destra"). La radice sara' identificata
dalla lista vuota, mentre, per esempio il nodo etichettato con 4
nell'albero sopra a sinistra e' identificato dalla lista (1 1), mentre la
lista (1 2) identifichera' il nodo con etichetta 5.
Definire una funzione SCHEME "listid" che, preso un albero del tipo visto sopra
restituisca la lista di tutte le liste che identificano le sue foglie.
Esempio: se T e' l'albero a sinistra dell'esempio allora
(listid T) = ((0 0) (0 2) (1 1) (1 2))
Una possibile soluzione.
Una possibile soluzione.
Esercizio 78
Definiamo nel seguente modo
il tipo di dato astratto Albero Ternario con etichette numeriche non negative.
(define emptytree '() )
(define (emptytree? tree)
(null? tree) )
(define (mktree label tree1 tree2 tree3)
(list label tree1 tree2 tree3) )
(define (label tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(car tree) ) )
(define (childleft tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(cadr tree) ) )
(define (childcenter tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(caddr tree) ) )
(define (childright tree)
(if (emptytree? tree)
(error "errore: operatore non applicabile")
(cadddr tree) ) )
(a)
Dato un albero del tipo sopra descritto ed un predicato unario su numeri,
possiamo identificare un
nodo dell'albero partendo dalla radice e
scendendo nell'albero con la seguente procedura:
se il predicato e' vero per l'etichetta del nodo, si scende a sinistra;
altrimenti, se il predicato e' vero per l'(etichetta+1), si scende al centro;
altrimenti si scende a destra.
Definire in SCHEME una funzione "scendi" che, preso un albero non vuoto ed un predicato
unario su numeri, restituisca l'etichetta del nodo identificato con la procedura
appena descritta.
Esercizio 79
Scrivere un'espressione Scheme la cui valutazione non termina, ma che
terminerebbe se fosse utilizzato l'interprete di Haskell.
Esercizio 80
Si supponga di non avere i numeri naturali come tipo di dato primitivo
in Haskell e Scheme. Definire in Haskell e Scheme il tipo di dato
NumeroNaturale.
Definire il predicato MaggUg? che,
presi due numeri naturali restituisce #t se e solo se il primo e'
maggiore o uguale al secondo. Se possibile, utilizzare il tipo di dato
definito prima, e comunque definire il predicato ricorsivamente facendo
uso solo del decremento di 1 e del test su 0.
Esercizio 81
Sappiamo che e' possibile trovare una funzione (invertibile) di codifica
tra le coppie di numeri naturali e i numeri naturali, utilizzando
il metodo del "dove tailing":
0 1 2 3 4 5 .....
0 <0,0><0,1><0,2><0,3>....
1 <1,0><1,1><1,2><1,3> ....
2 <2,0><2,1> .....
3 <3,0> ....
:
:
In questo modo, la coppia <0,0> vien codificata con 0, quella
<1,0> con 1, <0,1> con 2, <2,0> con 3, <1,1> con 4, etc...
E' facile vedere come tale codifica sia invertibile.
Si possono trovare le semplici espressioni aritmetiche che
definiscono le funzioni di codifica e decodifica.
Noi pero' siamo patiti della ricorsione e vogliamo definire
per ricorsione tali funzioni.
Una possibile soluzione.
Esercizio 82
Definire una relazione ben fondata sugli elementi dei domini delle
funzioni dell'esercizio 11 per dimostrare che le funzioni
risultano definite.
Esercizio 83
Descrivere graficamente la relazione di precedenza indotta dalla
seguente funzione Scheme sui numeri naturali. Tale relazione e' ben
fondata? Perche'?
(define (sgrunf n)
(if (< n 4)
71
(+ 5 (sgrunf (- n 3)))))
Esercizio 84
Definire in SCHEME il tipo di dato astratto Stack (nella sua versione puramente funzionale).
Definire le seguenti funzioni SCHEME che utilizzano tale tipo di dato:
Una possibile soluzione (riveduta da G. Narzisi).
Esercizio 85
Il seguente programma per risolvere il problema della torre di Hanoi
contiene due errori. Quali?
(define (tower-of-hanoi n peg1 peg2 peg3)
(if (= n 0)
'()
(cons (tower-of-hanoi (- n 1) peg1 peg3 peg2)
(cons (list peg1 peg2)
(tower-of-hanoi (- n 1) peg2 peg1 peg3)))))
Esercizio 86
(a) Definire in SCHEME il tipo di dato astratto Insieme. Utilizzando le
funzioni base del tipo Insieme definire le operazioni insiemistiche di
unione, intersezione,
differenza, differenza simmetrica, ecc. ecc.
Una possibile soluzione. (By C. Cherubino)
(b) Definire il tipo di dato insieme in Haskell.
Definire in Haskell alcune delle operazioni insiemistiche.
Esercizio 87
Supponiamo di aver definito il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set ia cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Definire una funzione SCHEME PowerSet che preso in input un insieme restituisca
il suo insieme delle parti (insieme potenza).
Es.: PowerSet({ 2, 5 }) = { {}, {2}, {5}, {2,5} }.
Se si vuole, si puo' supporre di aver anche gia' definito le funzioni
(union set1 set2) restituisce l'unione di set1 e set2
(add-all element SetOfSets) restituisce SetOfSets (che e' un insieme di insiemi) a cui
in ogni suo elemento e' stato aggiunto element.
Una possibile soluzione.
Esercizio 88
Definire il tipo di dato astratto Insieme-di-Naturali utilizzando per la sua
implementazione il teorema fondametale dell'aritmetica.
Esercizio 89
Si consideri la seguente funzione SCHEME che realizza la funzione di codifica nei numeri naturali
delle coppie di numeri naturali, utilizzando il metodo del "dove tailing":
(define (codifica n1 n2)
(if (= 0 n1 n2)
0
(+ 1
(codifica (if (= n2 0)
0
(+ n1 1))
(if (= n2 0)
(- n1 1)
(- n2 1))))))
Dimostrare per induzione che la funzione definita e' totale.
Una possibile soluzione.
Esercizio 90
Presa la seguente funzione SCHEME definita negli appunti sulla pagina web,
(define (change-value-at-n f n new-value)
(lambda (x)
(if (= x n)
new-value
(f x))))
si dica cosa fa la seguente funzione SCHEME "mistery", supponendo che i
suoi possibili argomenti siano funzioni che restituiscono sempre numeri non negativi.
(define (mistery f)
(if (= (f 7) 0)
0
(+ 10 (mistery (change-value-at-n f 7 (- (f 7) 1))))))
Scriverne una versione equivalente ma piu' semplice.
Fornire una relazione di precedenza sugli elementi del dominio di mistery
che sia ben fondata e che quindi permetta di dimostrare che "mistery" e
una funzione totale.
Esercizio 91
Consideriamo le seguenti funzioni SCHEME,
(define (change-values-at-n-and-m f n m new-value-n new-value-m)
(lambda (x)
(cond ((= x n) new-value-n)
((= x m) new-value-m)
( else (f x)))))
(define (minus-two-or-plus-one n boolean)
(if boolean
(- n 2)
(+ n 1)))
(define (mist f)
(if (< (+ (f 5) (f 6)) 100)
(lambda (x) x)
(lambda (x)
(+ x
((mist
(change-values-at-n-and-m
f
5
7
(minus-two-or-plus-one (f 5) #t)
(minus-two-or-plus-one (f 6) #f))) x)))))
L'argomento di mist puo' essere qualsiasi funzione da interi ad interi.
Fare uno a scelta dei seguenti esercizi.
1. Fornire una relazione di precedenza sugli elementi del dominio di mist che sia
ben fondata e che quindi permetta di dimostrare che "mist" e' una funzione totale. Cosa restituisce mist? meglio ancora: fornire una funzione SCHEME piu'
semplice ed equivalente.
2. Uguale ad 1. pero' sostituendo nel programma la condizione
(< (+ (f 5) (f 6)) 100) con (< (+ (f 5) (f 6)) (f 10))
Una possibile soluzione.
Esercizio 92
Definire in SCHEME il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set ia cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Definire la funzione SCHEME che fa l'unione di due insiemi.
Dire cosa fanno le seguenti funzioni SCHEME che utilizzano tale
tipo di dato.
(define (F f ins)
(if (emptyset? ins)
emptyset
(let ((el (pick ins)))
(union (f el) (F f (residue el ins))))))
(define (A el I)
(let ((first (pick I)))
(let ((second (residue first I)))
(add-elem
(add-elem (add-elem el first) (add-elem second emptyset))
(add-elem
(add-elem first (add-elem (add-elem el second) emptyset))
emptyset)))))
(define (B x)
(lambda (I)
(A x I)))
Definire la funzione che, preso un insieme di cardinalita'
maggiore o uguale a due restituisca l'insieme di tutte le sue partizioni in due.
(Per partizione in due di un insieme I intendiamo un insieme {C,D}
con C e D insiemi disgiunti e tali che I = C union D).
Una possibile soluzione.
Esercizio 93
Supponiamo di aver definito il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set a cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
-
Definire una funzione SCHEME "Trallallero" che prenda in input un numero intero n ed
un insieme I di funzioni unarie da interi ad interi
e che restituisca l'insieme composto dagli elementi ottenuti applicando ad n tutte le
funzioni di I.
ES.: (Trallallero 3 {inc, fact}) = {4, 6}
-
Definire una funzione SCHEME "Trallalla" che prenda in input un numero intero n ed
in insieme I di interi e restituisca una lista di due insiemi, il primo e' formato dagli
elementi di I minori di n, mentre il secondo da quelli maggiori od uguali ad n.
ES.: (Trallalla 3 {2, 6, 1, 3, 9}) = ({1,2}, {6,3,9})
N.B.:Non bisogna utilizzare funzioni locali o ausiliarie.
- Fornire una versione di "Trallallero" con ricorsione di coda.
Una possibile soluzione.
Esercizio 94
(a)
1. Definire in SCHEME il tipo di dato matrice quadrata di interi.
2. Definire in SCHEME il predicato su matrici quadrate
che indica se una matrice e' sparsa.
Supponiamo che una matrice sia sparsa se il numero di elementi uguali
a zero e' strettamente maggiore di quello degli elementi diversi da zero.
(b)
Che relazione esiste tra principi di induzione e la ricorsione?
Una possibile soluzione.
Esercizio 95
Supponete di aver definito in Scheme il tipo di dato astratto Lambda termine
che possiede i seguenti costruttori, selettori e predicati.
Costruttori:
(make-variable stringa): prende una stringa e la rende una variabile del lambda-calcolo.
(make-abstraction variable body):
prende un termine che e' una variabile, un lambda-termine e produce il lambda termine ottenuto
lambda-astraendo body rispetto variable
Selettori: (take-variable lambda-term): prende un lambda termine che e' una
lambda astrazione e restituisce la variabile astratta.
Predicati:
(is-variable? lambda-term);
(is-application? lambda-term);
Dire di quali altri costruttori, selettori e predicati abbiamo eventualmente bisogno per
definire correttamente il tipo di dato Lambda termine.
Supponete ora di avere a disposizione tutti i costruttori, selettori e predicati dati e quelli
che voi avete detto vanno eventualmente aggiunti.
Utilizzando anche il tipo di dato
MultInsieme (insiemi in cui un elemento puo' essere anche presente piu' volte)
descritto alla fine, definire una funzione SCHEME che preso un lambda termine
restituisca il multinsieme di tutti i suoi sottotermini che sono redex, cioe' che sono applicazioni
in cui il termine a sinistra e' una lambda astrazione.
Supponete di avere a disposizione anche la funzione union che restituisce
l'unione di due multinsiemi.
Il tipo di dato astratto MultInsieme ha i
seguenti
Costruttori:
emptyset il multinsieme vuoto;
(add-elem element set) restituisce il multinsieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set a cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Una possibile soluzione.
Esercizio 96
Definire in SCHEME il dato astratto "Tipo" (gli oggetti di questo tipo di dato astratto
rapresentano i tipi dei sistemi a' la Church e a' la Curry per il lambda-calcolo).
Scrivere una funzione SCHEME "substitute" che, preso un tipo T1, una variabile di tipo V
ed un altro tipo T2,
restituisca T1 in cui al posto di ogni occorrenza di V e' stato sostituito T2.
Dimostrare formalmente che substitute e' totale.
Una possibile soluzione.
Esercizio 97
Definire in Haskell i tipo di dato astratto Insieme e
il tipo di dato astratto LambdaTermine.
Scrivere una funzione Haskell che preso un lambda termine
restituisca l'insieme delle sue variabili legate.
Esercizio 98
Definire in Scheme e in Haskell il tipo di dato astratto
Numero Complesso e definire
in Scheme e Haskell la funzione "parte immaginaria" di un numero complesso.
Esercizio 99
Definire in Scheme e in Haskell il tipo di dato astratto
Numero Frazionario e definire
in Scheme e Haskell la funzione quadrato di un numero frazionario.
Esercizio 100
Definire in Scheme e in Haskell il tipo di dato astratto
Numero Frazionario e definire
in Scheme e Haskell il predicato IsZero? su numeri frazionari.
Esercizio 101
Definire in Scheme e in Haskell il tipo di dato astratto
Numero Frazionario e definire
in Scheme e Haskell la funzione che somma 1 un numero frazionario.
Esercizi 102
Fare gli esercizi dal 4.1 al 4.22 presenti nel testo [VS] Vladimiro Sassone, Induzione matematica e verifica di funzioni ricorsive
Possibili soluzioni.
Esercizio 103
Si consideri la seguente funzione Scheme che prende come input coppie di numeri naturali.
(define (Matrix n m)
(cond ((= m 0) m)
((= n 0) n)
(else (+ 1 (Matrix (- n 1) (Matrix n (- m 1)))))))
Dimostrare formalmente che la funzione Matrix e' totale.
Cosa calcola Matrix?.
Una possibile soluzione.
Esercizio 104
Definire in SCHEME il tipo di dato astratto Stack (nella sua versione puramente funzionale).
Definire una funzione SCHEME "perepe" che, preso in input uno Stack restituisce in output
lo Stack invertito.
Esempio informale:
| 1 | | 3 |
| 7 | | 7 |
(perepe | 3 | ) ---> | 1 |
----- -----
N.B. NON utilizzare ricorsione di coda.
Una possibile soluzione.
Esercizio 105
Si consideri la seguente funzione definita per ricorsione:
f(n) = f(n+1)+1 se 0 <= n < 100
f(n) = n altrimenti
Scrivere una funzione Scheme freak che calcoli f,
e si dimostri formalmente, per induzione ben
fondata, che
(freak n) = 100 + |100 - n|
Una possibile soluzione.
Esercizio 106
Si consideri la funzione
f (0,m) = m
f (n,m) = n * f (n-1,m+1)
Dimostrare per
induzione ben fondata che f (n,m) = (n+m) * n!
Una possibile soluzione.
Esercizio 107
Definiamo la relazione binaria << su numeri naturali come
segue:
n << m sse
n = m+3
Rappresentare graficamente la relazione e dire se e' ben fondata.
Esercizio 108
Dimostrare che il seguente programma Scheme definisce una
funzione totale su coppie di numeri interi.
(define (f x y)
(if (or (< x 5) (< y 5))
(+ x y)
(+ (f (- x 5) (* x x)) (f x (- y 3)))))
Esercizio 109
Supponiamo di aver definito il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set ia cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Definire una funzione SCHEME Intersection che presi in input due insiemi restituisca
l'insieme intersezione.
Esercizio 110
Supponiamo di aver definito il tipo di dato astratto Insieme che ha i
seguenti
Costruttori:
emptyset l'insieme vuoto;
(add-elem element set) restituisce l'insieme set a cui e' stato aggiunto element
Selettori:
(pick set) restituisce un elemento a caso di set;
(residue element set) restituisce set ia cui e' stato tolto element
Predicati:
(emptyset? set) vero se set e' l'insieme vuoto.
Definire un predicato SCHEME ForAll che, presi in input un insieme I ed un predicato P?,
verifichi se il predicato P? e' soddisfatto per tutti gli elementi di I.
Una possibile soluzione.
Esercizio 111
Si consideri l'insieme (N->N)xNxN, dove N e' l'insieme dei naturali e N->N quello delle
funzioni totali da N in N. Su tale insieme si consideri la seguente relazione:
(g,n,m) << (g',n',m') sse (n = n' e g(n) < g'(n')) oppure (n = n', g=g' e m < m')
Si dimostri che ((N->N)xNxN,<<) e' un insieme ben-fondato.
Si fornisca una qualsiasi funzione SCHEME la cui totalita' sia dimostrabile
utilizzando l'induzione ben-fondata su ((N->N)xNxN,<<).
Una possibile soluzione.
Esercizio 112
(define (YY? x y)
(cond ((= x y) #t)
((< x y) #f)
((> x y) (YY? (- x y) y))))
Dimostrare che il predicato YY? definito sopra e' totale. Dire per quali valori vale YY?
Riscrivere YY? utilizzando solo operatori booleani (senza utilizzare cond quindi).
Una possibile soluzione.