Haskell - Parcial 2017-12-04 P48366

Problema 1: Expressió postfixa 1

Escriviu una funció @eval1 :: String -> Int@ que avalui una expressió postfixa que es troba en una string. Els elements en l’expressió són valors (nombres naturals) i els operadors de suma, resta, producte i divisió. Els elements es separen per espais. Per exemple, l’avaluació de @"15 1 2 + 24 * + 3 -"@ és 84.

La solució canònica per evaluar expressions postfixes és utilitzar una pila: Començant per una pila buida, es processen els elements de l’expressió d’esquerra a dreta. Si l’element és un valor, s’empila. Si l’element és un operador, es desempilen dos valors, s’operen d’acord amb l’operador i s’empila el resultat. Al final, la pila conté un sol element, que és el resultat de l’evalaució de l’expressió.

Podeu suposar que no hi ha mai errors a l’expressió ni divisions per zero.

Solucioneu el problema recursivament. La funció @words@ us pot ser útil.

Problema 2: Expressió postfixa 2

Escriviu una funció @eval2 :: String -> Int@ que avalui una expressió postfixa com al Problema ‍1, però sense utilitzar recursivitat.

Problema 3: fsmap

Definiu una funció @fsmap :: a -> [a -> a] -> a@ que, donats un element @x@ de tipus @a@ i una llista @fs@ de funcions de tipus @a -> a@, fa que @fsmap x fs@ retorni l’aplicació (d’esquerra a dreta) de totes les funcions de @fs@ a @x@. Es valorà com de succinta és la vostra solució.

Problema 4: Dividir i vèncer

Escriviu una funció d’ordre superior que definixi l’esquema de dividir i vèncer i utilitzeu-la per fer l’algorisme de quicksort per a llistes d’enters.

La funció per dividir i vèncer ha de tenir aquesta interfície:

on @a@ és el tipus del problema, @b@ és el tipus de la solució, i @divideNconquer base divide conquer x@ utilitza:

• @base :: (a -> Maybe b)@ per obtenir la solució directa per a un problema si és trivial (quan és un @Just b@) o per indicar que no és trivial (quan és @Nothing@).
• @divide :: (a -> (a, a))@ per dividir un problema no trivial en un parell de subproblemes més petits.
• @conquer :: (a -> (a, a) -> (b, b) -> b)@ per, donat un problema no trivial, els seus subproblemes i les seves respectives subsolucions, obtenir la solució al problema original.
• @x :: a@ denota el problema a solucionar.

La funció pel quicksort ha de ser @quickSort :: [Int] -> [Int]@ i ha d’utilitzar @divideNconquer@.

Problema 5: Racionals

Definiu un tipus @Racional@ per manipular nombres racionals positius amb operacions per:

construir un racional a través d’un numerador i d’un denominador naturals, obtenir el numerador de la seva forma simplificada, obtenir el denominador de la seva forma simplificada.

A més, feu que @Racional@ pertanyi a la classe @Eq@ i a la classe @Show@, fent que els racionals es mostrin de la forma "x/y".

Seguiu aquesta interfície:

Si voleu, podeu utilitzar la funció estàndard @gcd@ que retorna el màxim comú divisor de dos naturals.

Problema 6: Arbre de Calkin-Wilf

L’arbre de Calkin–Wilf és un arbre binari que representa tots els racionals positius. L’arbre té com arrel el racional 1/1 i, qualsevol node a/b té dos fills a/(a + b) i (a + b)/b.

Aquests són els primers nivells de l’arbre de Calkin–Wilf: [figura extreta de Wikipedia]

Escriviu una funció @racionals :: [Racional]@ que retorni la llista infinita de tots els nombres racionals positius segons l’ordre de l’arbre de Calkin–Wilf.

Per a fer-ho, utilitzeu el tipus @Racional@ del problema anterior. També podeu aprofitar les definicions genèriques d’arbre infinit i del seu recorregut per nivells que es donen a continuació:

Important

El problema té diferents apartats. Cada apartat val 2 punts sobre 10 (però el Jutge en suma 12). Heu de resoldre 5 dels 6 apartats (no els 6!).