MiniHugs

Pràctiques de Haskell

1. Les pràctiques es fan en equips de dues persones. Heu de triar si feu una pràctica “fàcil” (7 punts sobre 10) o una de “menys fàcil” (10 punts). Llavors, poseu-vos en contacte amb el professor per indicar quina voleu fer. El professor us donarà la conformitat o us suggerirà una altra pràctica per tal que no tothom faci la mateixa.

2. Heu de lliurar un llistat amb les definicions de les funcions que hauran de tenir el NOM QUE S’INDICA a L’ENUNCIAT i la DEFINICIÓ DE TIPUS. Per a les definicions de tipus i funcions auxiliars feu servir el nom que vulgueu.

3. Si considereu que alguna funció que feu servir és quelcom “fosca”, expliqueu-la. Feu servir noms adients i doneu els tipus de totes les funcions.

4. Per a poder optar a la primera convocatòria, heu de lliurar la abans del 22 de juny.

5. Es valorarà positivament l’ús de funcions d’ordre superior i la instanciació dels tipus en diverses classes.

6. ATENCIÓ, heu de derivar els tipus principals de la pràctica de la classe Show usant INSTANCE no deriving.

Pràctiques

1) (7 punts)

A) Construeix un tipus de dades Arbrenari que sigui arbre n-ary “el més polimòrfic possible”, (per a qualsevol n).

· Defineix-ne una espècie de funció de plegament tipus fold per a les llistes, de manera que el pugui utilitzar per a definir:

o sumaarbre_n_ari : tal que donat un Arbrenari ens calculi la suma de tots els seus números, suposant que aquests siguin enters.

o mesgranarbre_n_ari: tal que donat un Arbrenari ens digui quin és el número més gran que hi apareix.

· Deriva’l correctament de la classe Eq i de la classe Show usant Instance.

· Defineix una funció amplada i que ens digui quina és l’amplada màxima d’un nivell i quins són els elements que la formen.

· Defineix la funció que fa recorregut en preordre preordre_n_ari.

B) Defineix el tipus Matriu i les següents funcions per al seu tractament:

1. transposa

2. suma

3. producte

deriva-la de la classe Show de manera que les mostri per pantalla en forma de matrius.

1) (7 punts)

A) Defineix el tipus Polinomi i les següents funcions per al seu tractament:

· suma

· producte

· resta

· valor que donat un polinomi i un real ens doni el valor de substituir al polinomi x pel real.

derivala de la classe Show de manera que les mostri per pantalla en forma de polinomis.

B) Fes el tipus Multiconjunt per a elements de la classe Eq i les següents funcions per al seu tractament:

· afegir

· treureun

· eliminar

· quantes_ocurrencies

· unio, interseccio, resta

· pertany

derivala de la classe Show de manera que les mostri per pantalla en forma de llista.

3) (10 punts) Construiu un tipus de dades Autodetregular que correspongui als autòmates regulars deterministes i un tipus Autoindetregular que correspongui als autòmates regulars indeterministes per al reconeixement de llenguatges regulars. Construeix-ne les funcions:

pertanydet: tal que donat un Autodetregular i una paraula, ens digui si pertany al llenguatge o no.

· pertanyindet: tal que donat un Autoindetregular i una paraula, ens digui si pertany al llenguatge o no.

· paraula: tal que donat un Autodetregular , ens torni una paraula reconeguda per l’autòmata (si és possible)

Deriveu-lo correctament de la classe classe Show

4) (10 punts) Definiu el tipus arbre binari Abin i deriveu-lo correctament de la classe classe Show :

construi-ne la funció rank: donat un Abin, ens diu quin rank te l’arbre segons la següent definició:

rank Fulla x               =0
rank Arrela x a1 a2     = rank a1 +1 si rank a1 = rank a2
                                             = max {Rank a1, Rank a2} altrament

Definiu també el tipus recorregut d’un Abin, que serà una llista de valors dels node visitats, indicant en quin ordre s’han recorregut, així, per exemple, un possible recorregut d’un arbre com:

f(f(a,b), c) === [(f,[1,2]), (f,[1,2]), (a,[]), (b,[]), (c, [])]

· Feu les funcions:

1. quinarbre: tal que donat un recorregut ens construeixi l’arbre del que n’és recorregut.

2. recorregutoptim: tal que donat un Abin, ens calculi el recorregut que passi primer pels subarbres de menys rank, i en cas d’igualtat, el de més a l’esquerra, indicant quina es la permutació que segueix, per exemple:

recorregutoptim f(f(a,b), c) === [(f,[2,1]) (c,[]) (f,[1,2]) (a,[]), (b,[])]

1. mateixarbre: tal que donats dos recorregut, ens digui si ho són del mateix arbre.

2. permdif: tal que donats dos recorreguts ens digui en quantes permutacions difereixen.

5) (10 punts) Definiu el tipus Lt (de Lambda-Terme) i deriveu-lo correctament de la classe show: (per la lambda useu “\” i per les variables “x1, x2...”):

Feu la funció betanorm tal que donat un Lt en trobi la seva forma normal.

Heu de ser capaços de definir els termes que hem vist a teoria i mostrar que el factorial de 3 és 6.

(compte, la versió d’anys anterior no val, ha de ser original!!! J)