Programmazione Funzionale e Parallela: Esercizi di preparazione all'esame: programmazione funzionale (A.A. 2015-2016)

Esercizi di preparazione all'esame: programmazione funzionale (A.A. 2015-2016)

Esercizio 1: massimo comun divisore

Si scriva una funzione Scala che calcola il massimo comun divisore (MCD) di due numeri interi. Usare la seguente definizione ricorsiva:

MCD(x,y)=x, se y=0
MCD(x,y)=MCD(y, resto della divisione di x per y) altrimenti

Soluzione:

def mcd(x:Int, y:Int):Int = if (y==0) x else mcd(y, x%y)

Esercizio 2: somma dei quadrati

Si scriva una funzione Scala che, dati due interi x e y con x<=y, calcola la somma dei quadrati dei numeri da x a y, compresi.

Soluzione:

def sommeQuad(x:Int, y:Int):Int = if (x>y) 0 else x*x + sommeQuad(x+1, y)

Esercizio 3: calcolo della radice quadrata approssimata

Un semplice metodo iterativo basato sul metodo di Newton per calcolare la radice quadrata di un numero x consiste nel partire da una stima iniziale y (es. y=1) e raffinarla successivamente calcolando la media tra y e x/y. Il procedimento termina quando il quadrato della stima è sufficientemente vicino a x.

Soluzione:

sqrt.sc

val epsilon = 0.0001

def abs(x:Double) = if (x<0) -x else x

def trovataBuonaStima(y:Double, x:Double) = abs(y*y-x) < epsilon

def stimaMigliore(y:Double, x:Double) = (y+x/y)/2.0

def raffinaSqrt(y:Double, x:Double):Double = if (trovataBuonaStima(y,x)) y else raffinaSqrt(stimaMigliore(y,x), x)

def sqrt(x:Double):Double = raffinaSqrt(1.0, x)

println("Radice quadrata di 2 ~ "+sqrt(2))

Si suggerisce di scomporre sempre un problema in funzioni più semplici. Questo non peggiora in pratica le prestazioni poiché il compilatore effettua inlining automaticamente, ma migliora molto la leggibilità, l'analisi di correttezza e la manutenibilità del codice.

Esercizio 4: test di primalità

Scrivere una funzione Scala che verifica se un numero è primo.

Soluzione:

Proposta da Kumalapalapandamaori:

prime.sc

def prime(n:Int) = if (n==1) false else primeRec(n, n/2)

def primeRec(n:Int, d:Int):Boolean = if (d==1) true else if (n%d == 0) false else primeRec(n, d-1)

Approfondimento:

La soluzione proposta richiede tempo O(n), quindi è esponenziale nella dimensione dell'input che è log n bit (numero di bit richiesti per rappresentare il numero n di input). Nel 2002, Manindra Agrawal, Neeraj Kayal e Nitin Saxena hanno dimostrato l'esistenza un algoritmo deterministico polinomiale (AKS). Per questa scoperta eccezionale, di interesse principalmente teorico essendoci algoritmi probabilistici più efficienti in pratica, hanno ricevuto il premio Gödel.

Ecco il leggendario articolo originale:
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

Queste slide trattano l'argomento in modo più divulgativo:
http://www.cs.unibo.it/~margara/page2/page6/page25/assets/primes.pdf

Esercizio 5: numeri di Fibonacci

Scrivere una funzione Scala che calcola l'n-esimo numero di Fibonacci F(n), dove F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, ecc.

Soluzione:

def fib(n:Int) = {
   def fibR(fa:Int, fb:Int, n:Int):Int = if (n <= 2) fb else fibR(fb, fa+fb, n-1)
   fibR(1,1,n)
}

Versione con verifica di ricorsione di coda da parte del compilatore:

def fib(n:Int) = {
   @scala.annotation.tailrec 
   def fibR(fa:Int, fb:Int, n:Int):Int = if (n <= 2) fb else fibR(fb, fa+fb, n-1)
   fibR(1,1,n)
}

Esercizio 6: ricorsione di coda

Si fornisca una variante della soluzione dell'Esercizio 2 che esibisce ricorsione di coda.

Soluzione:

def sommaQuad(x:Int, y:Int) = {
  @scala.annotation.tailrec
  def sommaQuadR(n:Int, x:Int, y:Int):Int = if (x>y) n else sommaQuadR(n+x*x, x+1, y)
  sommaQuadR(0, x, y)
}

Esercizio 7: uguaglianza parziale di funzioni

Scrivere una funzione Scala che, date due funzioni f1:Int=>Int e f2:Int=>Int e un intero n, verifica che f1 e f2 calcolino lo stesso valore su ogni input compreso tra 0 e n. La funzione deve restituire un Boolean.

Soluzione

def confronto(f1:Int=>Int,f2:Int=>Int,n:Int):Boolean = n<0 || f1(n)==f2(n) && confronto(f1, f2, n-1)

Esercizio 8: composizione di funzioni

Scrivere una funzione Scala componi che, date due funzioni f1:Int=>Int e f2:Int=>Int, restituisce una funzione f che compone f1 ed f2, calcolando f(x)=f1(f2(x)). Deve essere possibile eseguire questo programma:

val f = componi(x=>x*x, x=>x+1)
println(f(9)) // stampa 100

Esercizio 9: costruzione di funzioni per casi

Scrivere una funzione Scala concatena che, date tre funzioni f1:Double=>Double, f2:Double=>Double e f3:Double=>Double e due valori Double a e b con a<=b, restituisce una funzione che coincide con f1 per tutti gli argomenti prima di a, con f2 nell'intervallo [a,b], e con f3 dopo b.

Esercizio 10: funzione `map` su liste

Scrivere una funzione Scala ricorsiva map che, data una lista di interi l e una funzione f da interi su interi, restituisce una nuova lista ottenuta da l applicando a ciascun elemento la funzione f.

Esempio di uso:

val l = List(1,2,3,4)
val p = map(l, _*2)
println(p) // deve stampare List(2, 4, 6, 8)

Esercizio 11: funzione `filter` su liste

Scrivere una funzione Scala ricorsiva filter che, data una lista di interi l e un predicato f da interi su Booleani, restituisce una nuova lista ottenuta da l prendendo tutti e soli gli elementi per cui il predicato f vale.

Esempio di uso:

val l = List(1,2,3,4)
val p = filter(l, _>2)
println(p) // deve stampare List(3, 4)

Esercizio 12: funzione `partition` su liste

Scrivere una funzione Scala ricorsiva partition che, data una lista di interi l e un predicato f da interi su Booleani, restituisce una coppia di liste (a,b) dove a contiene gli elementi di l per cui il predicato f vale, e b gli altri.

Scrivere poi una variante non ricorsiva basata sul metodo filter.

Esempio di uso:

val l = List(1,2,3,4)
val (a,b) = partition(l, _%2==0) // separo i pari dai dispari
println(a) // deve stampare List(2, 4)
println(b) // deve stampare List(1, 3)

Esercizio 13: funzione `reverse` su liste

Scrivere una funzione Scala ricorsiva reverse che rovescia una lista di interi. E' possibile usare il metodo :+ per appendere un elemento alla fine di una lista (in tempo O(n), dove n=lunghezza della lista): esempio l:+7 aggiunge 7 alla fine della lista l. Discutere il tempo di esecuzione. E' possibile ottenere una realizzazione in tempo O(n)?

Soluzione

La soluzione richiede tempo e spazio O(n) e usa ricorsione di coda:

def reverse(l:List[Int]) = {
	@scala.annotation.tailrec
	def reverseR(l:List[Int], rev:List[Int]):List[Int] = {
		if (l.isEmpty) rev
		else reverseR(l.tail, l.head::rev)
	}
	reverseR(l, Nil)
}

Esercizio 14: funzione `equal` su liste

Scrivere una funzione Scala ricorsiva equal che verifica se due liste di interi sono uguali.

Esercizio 15: funzione `palindrome` su liste

Scrivere una funzione Scala ricorsiva palindrome che verifica se una lista di interi è palindroma. E' possibile usare il metodo last per accedere all'ultimo elemento alla fine di una lista e init per prendere la lista tranne l'ultimo elemento (in tempo O(n)). Discutere il tempo di esecuzione.

Scrivere una variante non ricorsiva che usa funzioni realizzate negli esercizi precedenti.

Esercizio 16: minimo e massimo di una lista

Scrivere una funzione Scala ricorsiva minMax che, data una lista non vuota di interi, restituisce una coppia (min,max), dove min e max sono il minimo e il massimo elemento della lista, rispettivamente.

Scrivere inoltre una variante non ricorsiva basata sui metodi standard della classe List visti a lezione.

Soluzione (ricorsiva)

def minMax(l:List[Int]) = {
	@scala.annotation.tailrec
	def minMaxR(l:List[Int], min:Int, max:Int):(Int, Int) = {
		if (l.isEmpty) (min, max)
		else if (l.head < min) minMaxR(l.tail, l.head, max)
		else if (l.head > max) minMaxR(l.tail, min, l.head)
		else minMaxR(l.tail, min, max)
	}
	minMaxR(l.tail, l.head, l.head)
}

Esercizio 17: verifica se una lista è ordinata

Scrivere una funzione Scala ricorsiva isOrd che verifica se una lista di interi è ordinata in modo crescente o decrescente.

Esercizio 18: funzione `reduce` su liste

Scrivere una funzione Scala ricorsiva reduce che, data una lista non vuota di interi l=List(v1, v2, v3,...) e una funzione f da coppie di interi su interi, restituisce f(...f(f(f(v1,v2),v3),v4)...).

Esempio di uso:

val x = reduce(List(1,2,3,4), _+_) // calcola 1+2+3+4
println(x) // deve stampare 10

Esercizio 19: funzione `equal` su liste usando pattern matching

Fornire una variante della funzione equal dell'esercizio 14 usando il costrutto match senza if ... else.

Suggerimento: fare match su una coppia di liste (si veda il capitolo pattern matching sulla dispensa)

Esercizio 20: classe per numeri razionali

Scrivere una classe Rational che rappresenta numeri razionali della forma num/den, dove num e den sono interi. Scrivere la classe in modo che sia possibile eseguire il seguente frammento Scala:

val r1 = new Rational(2, 7)
val r2 = new Rational(8, 6)
val r3 = new Rational(4,14)
println(r1+r2)  // stampa 34/21
println(r1-r2)  // stampa -22/21
println(r1*r2)  // stampa 8/21
println(r1/r2)  // stampa 3/14
println(r1==r3) // stampa true
println(r1!=r2) // stampa true
println(r1<r2)  // stampa true
println(r2<r1)  // stampa false

Suggerimento: calcolare il massimo comun divisore di numeratore e denominatore per riportare la frazione ai minimi termini (o irriducibile). Ad esempio, 4/14 dovrebbe essere memorizzato in un oggetto Rational come 2/7.

Esercizio 21: ricerca di un elemento in una lista

Scrivere una funzione generica find[T](x:T, l:List[T]):Boolean che, dato un elemento x, verifica se è presente nella lista l. Usare il costrutto match e non if ... else.

Esercizio 22: rimozione duplicati

Scrivere una funzione generica removeDuplicates[T](l:List[T]):List[T] che crea una nuova lista ottenuta da l rimuovendo gli elementi duplicati.

Esercizio 23: unione di liste

Scrivere una funzione generica union[T](l1:List[T], l2:List[T]):List[T] che costruisce l'unione di due liste. La lista restituita non deve contenere duplicati.

Esercizio 24: intersezione di liste

Scrivere una funzione generica intersection[T](l1:List[T], l2:List[T]):List[T] che costruisce l'intersezione di due liste. La lista restituita non deve contenere duplicati.

Soluzione:

ListOps.scala

object ListOps extends App  {

    def intersection[T](l1:List[T], l2:List[T]):List[T] =

        l1 match {

            case Nil => Nil

            case h::t if (l2 contains h) => h::intersection(t filter (_ != h), l2 filter (_ != h))

            case h::t => intersection(t filter (_ != h), l2)

        }

    println(intersection(List(1,2,3),List(2,5,6,3)))

    println(intersection(Nil,List(2,5,6,3)))

    println(intersection(List(1,2,3),List(2,1,3)))

}

Esercizio 25: disegno di un Mandala toroidale (grafica 2D)

Completare il metodo get dell'object ToroidalMandala seguente in modo che costruisca un modello 2D del Mandala toroidale a 24 "petali" mostrato in figura. La figura è creata utilizzando esclusivamente cerchi. La figura deve essere confinata nello spazio quadrato bidimensionale di lato unitario delimitato dall'origine degli assi fino al punto di coordinate (1,1). La figura viene poi scalata automaticamente dal modulo di visualizzazione per occupare la dimensione della finestra. Si ricordi che da Scala è possibile accedere a tutte le funzioni delle librerie Java (es. Math.sin).

Approfondimento. I Mandala sono dei disegni di grande suggestione che rivestono un significato spirituale e rituale sia nel Buddhismo che nell'Hinduismo. Il Mandala (dal sanscrito maṇḍala (मण्डल), tradotto come "cerchio") rapp