Questa sezione e' composta da due parti: ESERCIZI HASKELL e ESERCIZI PROGRAMMAZIONE HASKELL
ESERCIZI HASKELL
Esercizio 1

Definire in HASKELL 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).

  • Soluzione
    Esercizio 2

    Supponete di aver definito una funzione Haskell di nome funct.
    Dire cosa fa il sistema se si scrive: 
                                     :type  funct
    Dire cosa avrebbe fatto il sistema se prima della definizione di funct uno avesse scritto: 
                                     funct :: [Int] -> Bool

  • Soluzione
    Esercizio 3

    Definire in HASKELL il tipo di dato astratto Albero binario etichettato con etichette numeriche.

  • Soluzione
    Esercizio 4

    Definire in HASKELL il tipo di dato astratto Albero ternario senza etichette.

  • Soluzione
    Esercizio 5

    Definire in Haskell il tipo di dato Albero ternario etichettato. Discutere brevemente la soluzione proposta.

  • Soluzione
    Esercizio 6

    In Haskell ogni termine, prima di venire valutato, viene tipato con un sistema di assegnamento simile a quello a' la Curry visto nel corso. I lambda termini tipabili a' la Curry hanno la proprieta' di essere fortemente normalizzabili. Questo dovrebbe implicare che ogni "programma" Haskell "termini". Invece non e' cosi'.
    Cosa e' presente in Haskell in piu', rispetto al sistema di assegnamento di tipi a'la Curry per il lambda calcolo, che fornisce al linguaggio la possibilita' di avere non terminazione?

    Esercizio 7

    Supponendo che non sia predefinito, definire in HASKELL il tipo di dato astratto Lista di Interi. E' possibile definire il tipo di dato Lista di elementi qualsiasi?

  • Soluzione
    Esercizio 8

    Cosa ha a che fare il lambda-calcolo tipato a' la Curry con HASKELL? Discutere.

    Esercizio 9

    La sonda Spirit ha trovato che su Marte esistono i Loffioni.
    Un Loffione puo' essere un Gangarone oppure un Sarrapone, oppure una sequenza finita di Purpuroni. Un Purpurone e' formato da un Gangarone e un Sarrapone. In natura il numero di sarraponi e' infinito, invece esistono solo due Gangaroni, il GangaroneA e il GangaroneB.
    Definire in Haskell il tipo di dato astratto Loffione che possa permettere di scrivere programmi Haskell che simulino esperimenti virtuali sui Loffioni.

  • Soluzione
    Esercizio 10

    Le seguente definizioni HASKELL 
    f n = n:(f(n+1))
nums = f 0
    corrispondono, in SCHEME, a 
    (define (f n)  (cons n (f (+ n 1))))
(define nums (f 0))
    Che cosa "dovrebbe" fare f? e cosa e' nums?
    Perche' in Haskell possiamo utilizzare f e nums (fornire possibilmente un esempio di uso), mentre in SCHEME non ci possiamo fare in pratica niente?
    Perche' comunque, anche se poi non ci possiamo fare un fico secco, SCHEME permette lo stesso di definire la funzione f senza darci problemi?

  • Soluzione
    Esercizio 11

    Presa la seguente definizione di tipo in HASKELL 
    	data Pirimpo = Pompero Int | Zumpo Pirimpo [Int]
    scrivere delle definizioni Scheme che permettano di utilizzare (per qual che e' possibile in Scheme) il tipo di dato Pirimpo.

  • Soluzione
    Esercizio 12
    Gli Yunz sono esseri magici che nella contea di Hargaar vengono usati dagli studenti per passare gli esami.
    Uno Yunz puo'  venire generato dicendo due numeri qualsiasi mentre si effettua l'incantesimo del mago Frunz su due Yunz. Il nanetto Yor e' uno Yunz.
  • Soluzione
    Esercizio 13

    Dire brevemente cosa fa' l'interprete HASKELL quando scriviamo qualcosa del genere: 
    	funct :: [Int] -> Bool
		
	funct ls = BODY
    Esercizio 14
    Si considerino le seguenti definizioni Haskell contenure in un file di nome esercizio.hs. 
    contains x [] = False
contains x (y:ys) = if (x == y) then True else (contains x ys)

data Giuggiolo = Giuggiolo Int
  deriving(Show)

data Paperino = Paperosimple Giuggiolo | Paperocomplex  [Giuggiolo]
  deriving(Show)

cucu :: Paperino -> Giuggiolo -> Bool

cucu (Paperosimple (Giuggiolo n)) (Giuggiolo m) = (n == m)

cucu (Paperocomplex lg) g = (contains g lg)
    Se facciamo valutare il file esercizio.hs all'interprete Haskell riceviamo la seguente segnalazione di errore: 
    ERROR "esercizio.hs":17 - Instance of Eq Giuggiolo required for definition of cucu
    Perche'? Come si risolve il problema?
  • Soluzione
    Esercizio 14
    Descrivere in generale il concetto di overloading nei linguaggi di programmazione. Descrivere poi come questo viene implementato nelle Type Classes di Haskell. Descrivere inoltre sintassi ed uso delle Type Classes in Haskell.
    Esercizio 15
    Monadi in Haskell. Definizione e loro utilizzo.
    Esercizio 16
    Discutere brevemente dell'uso dell'algoritmo di unificazione nell'interprete Haskell ed in quello Prolog.
    Esercizio 17
    Definire la nozione di Pattern matching ed il suo utilizzo in Haskell.
    In quale altro linguaggio studiato nel corso viene utilizzata la nozione di pattern matching?
    In generale, in cosa differiscono i concetti di Pattern matching e di Unificazione? Esercizio 18
    Cosa restituisce Haskell se forniamo all'interprete la seguente espressione? 
    :type (>>=)
    Quando viene utilizzato in Haskell l'operatore >>= ?
    Esercizio 19
    Si consideri la seguente funzione Haskell: 
    myPenultimo (x) |  (length x)==1  = x
                |  (length x)==2  = head x
                |  otherwise      = myPenultimo(tail x)
    L'interprete restituisce il seguente errore 
    Occurs check: cannot construct the infinite type: a0 = [a0]
    Expected type: [[a0]]
      Actual type: [a0]
    In the first argument of `head', namely `x'
    In the expression: head x
    In an equation for `myPenultimo':
        myPenultimo (x)
          | (length x) == 1 = x
          | (length x) == 2 = head x
          | otherwise  = myPenultimo (tail x)
Failed, modules loaded: none.
    Perche'?
    Modificare inoltre la funzione in modo che restituisca il penultimo elemento di una lista (definendo penultimo di [] come [] e penultimo di una lista con un solo elemento come l'unico l'elemento).

  • Soluzione




    ESERCIZI PROGRAMMAZIONE HASKELL



    Esercizio 1

    Scrivere la funzione Haskell "pippo" che corrisponde al lambda termine 
                  \xy.yx
    Come si puo' fare in modo che, senza modificare la definizione della funzione pippo, questa possa accettare solo elementi numerici come primo input?
  • Possibile soluzione.
    Esercizio 2

    Definire una funzione Haskell ricorsiva che prenda in input un numero naturale n e calcoli la somma di tutti i numeri pari da 0 a n. (Usare il predicato Haskell che controlla se un numero e' pari  )
    Esercizio 3

    Definire in Haskell la funzione "manoh" che, preso un numero n, restituisce la somma dei quadrati dei naturali da 0 ad n.
    Esercizio 4

    Definire in Haskell la funzione "mavah" che, preso un numero n, restituisce il quadrato della somma dei naturali da 0 ad n.
    Esercizio 5

    Definire in Haskell la funzione "madaih" che, preso un numero n, restituisce la somma dei naturali da 0 ad n.
    Esercizio 6

    Definire in Haskell 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 Haskell 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 8
    Definire il tipo di dato Simple Type ed implementare l'algoritmo di unificazione tra Simple Types.
  • Possibile soluzione.
    Esercizio 8.1
    Modificare la funzione unifyTypes della soluzione dell'esercizio 8 in modo che l'unificazione di due tipi restituisca una coppia di tipo (TypeSubst,Bool) tale che il valore booleano sia falso1 se e solo se i tipi non siano unificabili (in questo caso il valore della sostituzione deve essere la funzione identita').
  • Possibile soluzione.
    Esercizio 9
    Definire una semplice classe ed una sua istanza.
  • Possibile soluzione.
    Esercizio 10
    Definire alcuni tipi di dati albero (possibilmente parametrici). Per esempio, alberi binari etichettati, alberi ternari, alberi con numeri arbitrari di figli ecc.
    Identificare poi alcune operazioni che possano essere utilizzate su ognuno di tali tipi, per esempio l'altezza.
    Definire quindi una classe Tree con tali operazioni, definendo i tipi precedentemente forniti come istanze di tale classe.
    Esercizio 11
    Definire la funzione Haskell che implementi l'insertion sort su liste, avendo come parametro anche la relazione di precedenza.
  • Possibile soluzione.
    Esercizio 12 (un po' complesso)
    Definire la funzione Haskell che, dato un grafo e due nodi, restituisca l'insieme dei cammini (privi di cicli) dal primo al secondo nodo.
  • Possibile soluzione.
    Esercizio 13
  • Definire in Haskell i tipi di dato Abn ("Albero binario con etichette numeriche") e Abf ("Albero binario con etichette di tipo Int -> Int"). Definire due semplici elementi di tipo Abn e Abf.
  • Definire una funzione Haskell 
    appT :: Abf -> Abn -> Abn
    che prenda un albero Abf ed uno Abn con la stessa struttura (non occorre implementare il controllo che abbiano la stessa struttura) e restituisca un albero Abn (con la stessa struttura degli alberi in input) in cui le etichette corrispondano alle applicazioni delle funzioni dell'albero Abf ai numeri dell'albero Abn.
  • Nel caso di alberi con struttura differente, e volendo gestire tale situazione non con la generazione di un messaggio di errore, si potrebbe utilizzare la monade Maybe. Ridefinire quindi la funzione appT in modo che abbia il seguente tipo 
    appT :: Abf -> Abn -> (Maybe Abn)

  • Possibile soluzione.
    Esercizio 14 Definire in Haskell il tipo di dato Lambda-Termine e realizzare le funzioni fv e bv che calcolano gli insiemi delle variabili, rispettivamente, libere e legate di un termine.
    Per realizzare fv e bv si utilizzi il dato 
    data Set a = Set [a]
    e si supponga di avere a disposizione gli operatori insiemistici "union" e "minus".
  • Possibile soluzione.
    Esercizio 15 Definire in Haskell la lista di tutti i numeri naturali a partire da 1.
    Utilizzarla per definire la funzione che, preso un predicato sui numeri, restituisca la lista di tutti i numeri che soddisfano il predicato.
  • Possibile soluzione.
    Esercizio 16 Utilizzare l'esercizio 15 per definire la lista di tutti i multipli comuni a due numeri e da questa la funzione che calcoli il minimo comune multiplo.
  • Possibile soluzione.
    Esercizio 17 Definire il tipo di dato parametrico degli alberi etichettati in cui ogni nodo puo' avere un numero arbitrario di figli.
    Definire quindi la funzione innesta che, presa in input un'etichetta label e due alberi, inserisca il secondo albero come primo figlio di tutti i nodi del primo albero che hanno label come etichetta.
    Rendere il tipo di dato membro della classe Eq, in modo che sugli alberi la funzione di uguaglianza corrisponda all'uguaglianza della loro struttura, senza considerare le etichette.
  • Possibile soluzione.
    Esercizio 18 La seguente funzione Scheme prende in input un predicato su numeri una lista ls contenente numeri o liste di numeri a qualsiasi livello di annidamento e restituisce una lista uguale ad ls, ma con 0 al posto dei numeri che soddisfano il predicato p? 
    define (guess p? ls)
  (if (null? ls)
      '()
      (cons (cond
              ( (not (number? (car ls)))   (guess p? (car ls)) )
              ( (p? (car ls)) 0 )
              (  else (car ls) ) )
            (guess p? (cdr ls)) ) ) )
    Scrivere una funzione Haskell che faccia la stessa cosa.
  • Possibile soluzione.
    Esercizio 19 Definire in Haskell la lista di tutti i numeri naturali a partire da 1.
    Utilizzarla per definire la funzione che, preso un predicato sui numeri, restituisca la lista di tutti i numeri che soddisfano tale predicato.
    Esercizio 20 La sonda Spirit ha trovato che su Marte esistono i Loffioni.
    Un Loffione puo' essere generato da un Gangarone oppure da un Sarrapone, oppure da una sequenza finita di Purpuroni. Un Purpurone viene generato dall'incontro di un Gangarone e un Sarrapone. Su Marte ci sono infiniti sarraponi, ma solo due Gangaroni, il GangaroneA e il GangaroneB.
    Definire in Haskell il tipo di dato astratto Loffione che possa permettere di scrivere programmi Haskell che simulino esperimenti virtuali sui Loffioni.
    Scrivere il programma Haskell che, preso un Loffione, restituisca quante volte il GangaroneA e' intervenuto nella generazione del Loffione dato.
  • Possibile soluzione.
    Esercizio 21 Definire in Haskell il tipo delle funzioni parziali da Interi ad Interi.
    Definire la funzione "comp" che, prese due funzioni parziali da interi ad interi, restituisca la loro composizione.
    Definire inoltre la funzione "union" che, prese due funzioni parziali da interi a interi f e g restituisca, con input x, f(x) se f e' definita su x, g(x) altrimenti.
  • Possibile soluzione.
    Esercizio 22 Supponiamo, per semplicita', che in Pict un valore possa essere un intero, un canale o una tupla (anche vuota) di valori. Sempre per semplicita', supponiamo che un pattern Pict possa essere una variabile o una tupla (anche vuota) di pattern.
    Definire in Haskell: Il pattern matching, se ha successo, sappiamo che restituisce un binding. Si puo' scegliere di definire un binding come una funzione parziale (nello stile dell'esercizio 1.a), oppure come una lista di coppie, o in qualche altro modo che preferite. Per semplicita' si puo' supporre che il fallimento di un matching provochi un errore, ma potete scegliere altre alternative.
  • Possibile soluzione.
    Esercizio 23 Supponiamo di aver bisogno, dati due tipi A e B, di lavorare con liste contenenti elementi di A e B alternati.
    Definire in Haskell tale tipo di dato. Utilizzarlo poi per definire una funzione "divide" che, presa una lista ls di Int e Bool alternati, restituisca la coppia formata dalle due liste ottenute considerando solo gli elementi Int e quelli Bool in ls.
    Il tipo coppia e' denotato in Haskell con (T1,T2). Il costruttore di coppie e', similmente, (e1,e2). "fst" e' la funzione che restituisce il primo elemento di una coppia, "snd" il secondo.
  • Possibile soluzione.
    Esercizio 24 Discutere brevemente della Tail Recursion.
    Il seguente codice Haskell implementa l'insertion-sort parametrizzato sul un predicato di precedenza, prec. 
    insert el [] prec = [el]
insert el (x:xs) prec = if (prec el x) 
                         then (el:(x:xs))
                         else (x:(insert el xs prec))


insertionsort [] prec = []
insertionsort (x:xs) prec = (insert x (insertionsort xs prec) prec)
    Fornire una versione tail-recursive dell'insertion-sort.
    (se servissero, si puo' supporre di avere a disposizione le versioni tail-recursive dell'append e del reverse: appendIt e reverseIt).
  • Possibile soluzione.
    Esercizio 25 Scrivere un programma Haskell che produca la lista di tutti i possibili cammini tra due nodi forniti in input in un grafo non orientato (anch'esso fornito in input).
    Il grafo e' rappresentato da una lista di archi, rappresentati a loro volta da coppie di nodi. I nodi sono rappresentati da numeri interi. Si supponga che se un arco e' rappresentato dalla coppia (n,m), allora il grafo non contiene anche la coppia (m,n). archi
  • Possibile soluzione.
    Esercizio 25.1 Modificare il programma dell'esercizio 25 definendo il tipo grafo come 
     
type Graph = (Set Node, (Node -> (Set Node)))


    Esercizio 26 Si fornisca una soluzione dell'esercizio 25 in modo che la chiamata ricorsiva del programma abbia sempre lo stesso grafo come argomento.
  • Possibile soluzione.
    Esercizio 27 In Haskell, il costruttore di tipo lista e' una monade. Dare un'occhiata a tale monade nel testo e poi modificare la soluzione dell'esercizio 25 utilizzando l'operatore >>= per rendere piu' compatta tale soluzione.
  • Possibile soluzione.
    Esercizio 28 Fornire una soluzione che usi ricorsione di coda per l'esercizio 25.
  • Possibile soluzione.
    Esercizio 29 Definire in Haskell il tipo di dato astratto Albero Binario con rami infiniti e con nodi con etichette di tipo parametrico a.
    Costruire poi l'albero infinito con etichette numeriche della forma: 
                            
                          1
                         / \
                        /   \
                       /     \
                     2         3
                   /  \       /  \
                 4      5     6   7
                / \    / \   / .......
               8   9  10 11 12 ........
               .......................

  • Possibile soluzione.
    Esercizio 30 Sia    data InfNBT = Join Int InfNBT InfNBT
    il tipo di dato degli alberi binari con rami infiniti ed etichette numeriche.
    Si definisca myIT come il seguente elemento di InfNBT 
                            
                          1
                         / \
                        /   \
                       /     \
                     2         3
                   /  \       /  \
                 4      5     6   7
                / \    / \   / .......
               8   9  10 11 12 ........
               .......................
    e poi si definisca la funzione levelOrder :: InfNBT → [Int] che restituisce la lista delle etichette di un albero infinito ordinate livello per livello da sinistra a destra.
    Per esempio, la valutazione di (levelOrder myIT) produrra' la lista infinita di tutti gli interi a partire da 1.
    (Una possibile soluzione potrebbe utilizzare una funzione che, preso un albero ed un numero n, restituisca la lista di tutti i sottoalberi di livello n)
    Si scriva inoltre la piu' breve espressione Haskell il cui valore e' la lista di tutti gli interi a partire da 1.
  • Possibile soluzione.
    Esercizio 31 Definire un tipo di dato astratto i cui elementi rappresentino termini PROLOG.
    Inserire il tipo di dato nella classe Show in modo che i suoi elementi vengano visualizzati esattamente come termini PROLOG.
    Estendere a tali termini la funzione unify dell'esercizio 8.1
  • Possibile soluzione.
    Esercizio 32 Scrivere un programma Haskell che riconosca o rifiuti stringhe appartenenti al linguaggio regolare, sull'alfabeto {a,b,c}, associato alla seguente espressione regolare
    abc*b + aa
    Ricordiamo che il tipo String in Hakell coincide con [Char] e che un carattere si rappresenta tra apici (es.: 'a').
  • Possibile soluzione.
    Esercizio 33 La seguente funzione Erlang firstList2secondList prende due liste non vuote di uguale lunghezza e restituisce una funzione che, preso un elemento della prima lista restituisce l'elemento della seconda lista nella stessa posizione.
    In Erlang la funzione predefinita lists:nth(N,L) restituisce l'N-esimo elemento della lista L. Inoltre la funzione position prende un elemento ed una lista che lo contiene e restituisce la sua posizione. Notare inoltre l'uso di "fun" per denotare una funzione anonima.
    firstList2secondlist(First,Second) -> 
              fun(Elem) -> N = position(Elem,First);
	                   lists:nth(N,Second)
	      end.
    Scrivere la stessa funzione in Haskell, senza utilizzare funzioni ausiliarie come position e lists:nth.
    Fornire il tipo principale calcolato da Haskell per la funzione definita.
    Come mai in Haskell e' possibile fornire la funzione richiesta in modo semplice ed elegante, mentre in Erlang cio' risulterebbe piu' complesso?
  • Possibile soluzione.
    Esercizio 34 Si consideri il seguente codice Haskell incompleto 
    data ......

treeapply f (Leaf x) = x

treeapply  f (Node n t1 t2) = f n (treeapply f t1) (treeapply f t2)
    e si completi con la definizione del tipo di dato in modo che questa risulti la piu' generale possibile.
    Cosa calcola la funzione treeapply?
    Cosa restituisce l'interprete se chiediamo la cosa seguente? 
    :type treeapply
    Giustificare la risposta.
  • Possibile soluzione.
    Esercizio 35 Supponiamo di aver definito in Haskell un tipo Var che rappresenti un insieme infinito di variabili, ed un tipo Value che rappresenti un insieme di valori.
    Usare la monade Maybe per definire il tipo dei "bindings" che sono associazioni tra un numero finito di variabili e valori. Definire una funzione update che, dato un binding B, una variabile var ed un valore val, restituisca un binding che si comporta come B, ma che su var restituisce val. (Si puo' assumere che il tipo Var sia nella classe Eq).
  • Possibile soluzione.
    Esercizio 36 Definire in Haskell il tipo di dato "termine Prolog" ed inserirlo nella classe Show in modo da vedere sullo schermo i suoi elementi come se fossero reali termini Prolog.
  • Possibile soluzione.
    Esercizio XX
  • Possibile soluzione.