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:

    divideNconquer :: (a -> Maybe b) -> (a -> (a, a)) -> (a -> (a, a) -> (b, b) -> b) -> a -> b

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:

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:

    data Racional = ...
    racional :: Integer -> Integer -> Racional
    numerador :: Racional -> Integer
    denominador :: Racional -> Integer

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ó:

    data Tree a = Node a (Tree a) (Tree a)
    recXnivells :: Tree a -> [a]
    recXnivells t = recXnivells' [t]
        where recXnivells' ((Node x fe fd):ts) = x:recXnivells' (ts ++ [fe, fd])

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!).