Haskell - Parcial 2018-11-06 P24239


Statement
 

pdf   zip

html

1. Nombres romans (amb recursivitat)

Definiu una funció roman2int :: String -> Int que converteixi un número romà al seu enter equivalent tot usant recursivitat.

Recordeu que els números romans s’escriuen amb els símbols I, V, X, L, C, D i M, amb valors 1, 5, 10, 50, 100, 500 i 1000 respectivament. En aquest sistema, per obtenir el nombre representat, se sumen els valors dels símbols, excepte els símbols situats a l’esquerra d’un símbol de valor més gran, que es resten.

2. Nombres romans (sense recursivitat)

Definiu una funció roman2int’ :: String -> Int que faci el mateix que la funció anterior però sense usar recursivitat: useu una o més funcions d’ordre superior.

3. Arrels

La sèrie de Taylor per calcular √x és:

     
f1(x)=x          
fn(x)
=
1
2



fn−1(x)+
x
fn−1(x)



         

Definiu una funció arrels :: Float -> [Float] que, donat un real x, retorni la llista infinita dels termes del desenvolupament de Taylor de √x.

4. Més arrels

Escriviu una funció arrel :: Float -> Float -> Float que a partir d’una x i un є, aproximi l’arrel de x amb un error inferior o igual a є utilitzant la llista infinita anterior. L’error en el terme ti de la sèrie (amb i>1) és la diferència en valor absolut entre ti i ti−1.

5. Escriptura d’arbres

Considereu el següent tipus genèric LTree a d’arbres binaris amb valors a les fulles:

   data LTree a = Leaf a | Node (LTree a) (LTree a)

Feu que els arbres siguin instàncies de la classe Show visualitzant-se segons els exemples.

6. Creació d’arbres equilibrats

Feu una funció build :: [a] -> LTree a que, donada una llista no buida, construeix el LTree equilibrat (a l’esquerra) que conté els elements de la llista en el mateix ordre d’esquerra a dreta. Diem que un arbre es equilibrat a l’esquerra si tots els subarbres tenen el fill esquerre amb la mateixa profunditat que el fill dret o la mateixa més 1.

7. Mònades i arbres

Definiu una funció zipLTrees :: LTree a -> LTree b -> Maybe (LTree (a,b)) que combini els valors de les fulles de dos arbres amb la mateixa estructura.

Si les estructures dels dos arbres no encaixen, retorna Nothing i, si encaixen, retorna Just de l’arbre que té a cada fulla el parell amb el primer element del primer arbre i el segon del segon arbre en la mateixa posició.

Utilitzeu la notació do.

Public test cases
  • Input

    roman2int "I"
    roman2int "IV"
    roman2int "MCCCXIX"
    roman2int "MMXVIII"
    

    Output

    1
    4
    1319
    2018
    
  • Input

    roman2int' "I"
    roman2int' "IV"
    roman2int' "MCCCXIX"
    roman2int' "MMXVIII"
    

    Output

    1
    4
    1319
    2018
    
  • Input

    take 10 $ arrels 4.0
    take 10 $ arrels 100.0
    

    Output

    [4.0,2.5,2.05,2.0006099,2.0,2.0,2.0,2.0,2.0,2.0]
    [100.0,50.5,26.240099,15.02553,10.840435,10.032578,10.000053,10.0,10.0,10.0]
    
  • Input

    arrel 4.0 0.00001
    arrel 100.0 0.1
    

    Output

    2.0
    10.000053
    
  • Input

    Node (Leaf 3) (Node (Leaf 8) (Leaf 7))
    Node (Leaf 1) (Node (Node (Leaf 3) (Leaf 4)) (Node (Leaf 8) (Leaf 7)))
    Node (Leaf "Albert") (Node (Leaf "Gerard") (Leaf "Jordi"))
    Leaf 'x'
    

    Output

    <{3},<{8},{7}>>
    <{1},<<{3},{4}>,<{8},{7}>>>
    <{"Albert"},<{"Gerard"},{"Jordi"}>>
    {'x'}
    
  • Input

    build [3, 2, 5]
    build [3, 2, 8, 5, 1]
    build ['a', 'b', 'c', 'd']
    build [[1, 2, 3]]
    

    Output

    <<{3},{2}>,{5}>
    <<<{3},{2}>,{8}>,<{5},{1}>>
    <<{'a'},{'b'}>,<{'c'},{'d'}>>
    {[1,2,3]}
    
  • Input

    let t1 = Node (Leaf "a") (Node (Leaf "b") (Leaf "c"))
    let t2 = Node (Leaf 0) (Node (Leaf 1) (Leaf 2))
    let t3 = Node (Node (Leaf 1) (Leaf 2)) (Leaf 0)
    zipLTrees t1 t2
    zipLTrees t1 t3
    

    Output

    Just <{("a",0)},<{("b",1)},{("c",2)}>>
    Nothing
    
  • Information
    Author
    Jordi Petit, Albert Rubio, Gerard Escudero
    Language
    Catalan
    Other languages
    Spanish
    Official solutions
    Haskell
    User solutions
    Haskell