Examen parcial Haskell 2017-12-04

solucio.hs

-- ------------------------------------------------
-- Apartat 1 
-- ------------------------------------------------

eval1 :: String -> Int
eval1 e = eval' [] $ words e
    where
        eval' :: [Int] -> [String] -> Int
        eval' [x] [] = x
        eval' (a:b:p) ("+":ws) = eval' ((+) b a : p) ws
        eval' (a:b:p) ("-":ws) = eval' ((-) b a : p) ws
        eval' (a:b:p) ("*":ws) = eval' ((*) b a : p) ws
        eval' (a:b:p) ("/":ws) = eval' (div b a : p) ws
        eval' p (num:ws) = eval' (read num : p) ws


-- ------------------------------------------------
-- Apartat 2 
-- ------------------------------------------------

eval2 :: String -> Int
eval2 e = head $ foldl f [] (words e)
    where
        f :: [Int] -> String -> [Int]
        f (a:b:p) "+" = (+) b a : p
        f (a:b:p) "-" = (-) b a : p
        f (a:b:p) "*" = (*) b a : p
        f (a:b:p) "/" = div b a : p
        f p num = read num : p

-- ------------------------------------------------
-- Apartat 3
-- ------------------------------------------------

fsmap :: a -> [a -> a] -> a
fsmap = foldl $ flip ($)


-- ------------------------------------------------
-- Apartat 4
-- ------------------------------------------------

divideNconquer :: (a -> Maybe b) -> (a -> (a, a)) -> (a -> (a, a) -> (b, b) -> b) -> a -> b
divideNconquer base divide conquer x =
    case base x of
        Just y      -> y
        Nothing     -> conquer x (x1, x2) (y1, y2)
                            where
                                (x1, x2) = divide x
                                y1 = divideNconquer base divide conquer x1
                                y2 = divideNconquer base divide conquer x2


quickSort :: [Int] -> [Int]
quickSort = divideNconquer qsBase qsDivide qsConquer
    where
        qsBase :: [Int] -> Maybe [Int]
        qsBase []   = Just []
        qsBase [x]  = Just [x]
        qsBase _    = Nothing

        qsDivide :: [Int] -> ([Int], [Int])
        qsDivide (x:xs) = (lts, gts)
            where
                lts = filter (<=x) xs
                gts = filter (> x) xs

        qsConquer :: [Int] -> ([Int], [Int]) -> ([Int], [Int]) -> [Int]
        qsConquer (x:_) _ (ys1, ys2) = ys1 ++ x : ys2


-- ------------------------------------------------
-- Apartat 5
-- ------------------------------------------------

data Racional = Rac Integer Integer

racional    :: Integer -> Integer -> Racional
numerador   :: Racional -> Integer
denominador :: Racional -> Integer

racional num den = Rac (div num mcd) (div den mcd)
    where mcd = gcd num den

numerador   (Rac num den) = num
denominador (Rac num den) = den

instance Eq Racional where
    r1 == r2 = numerador r1 == numerador r2 && denominador r1 == denominador r2

instance Show Racional where
    show r = (show $ numerador r) ++ "/" ++ (show $ denominador r)


-- ------------------------------------------------
-- Apartat 6 
-- ------------------------------------------------

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])

racionals :: [Racional]
racionals = recXnivells $ arbre (racional 1 1)
    where
        arbre r = Node r (arbre fe) (arbre fd)
                        where
                            fe = racional a (a+b)
                            fd = racional (a+b) b
                            a  = numerador r
                            b  = denominador r
                            

Suposo que el Eq també es podia fer amb un deriving (Eq) perquè sempre es contrueixen els valors amb la funció racional que ja els desa simplificats.