Haskell - Arbres amb talla P58738


Statement
 

pdf   zip

thehtml

Considereu aquesta definició de tipus algebraic genèric per a arbres binaris amb talla (nombre de nodes del subarbre a cada node):

  1. Escriviu una funció isOk :: STree a -> Bool que indiqui si les talles dels nodes d’un arbre amb talles són correctes.
  2. Escriviu una funció nthElement :: STree a -> Int -> Maybe a que retorni l’n-èsim element en inordre (començant per 1) d’un arbre amb talla correcte, o Nothing si no existeix. El cost ha de ser O(h) on h és l’alçada de l’arbre.
  3. Escriviu una funció mapToElements :: (a -> b) -> STree a -> [Int] -> [Maybe b] que aplica (potser) una funció a una llista d’elements d’un arbre amb talla correcte (identificats per la seva posició en inordre).
  4. Feu que STree sigui un functor.

Fixeu-vos en els exemples.

Public test cases
  • Input

    let div10 = flip div 10
    let t1 = Node 3 99 (Node 1 88 Nil Nil) (Node 1 22 Nil Nil)
    let t2 = Node 2 77 (Node 1 33 Nil Nil) Nil
    let t3 = Node 6 44 t1 t2
    let t4 = Node 7 55 t1 t2
    isOk t3
    isOk t4
    nthElement t3 1
    nthElement t3 9
    nthElement t3 3
    nthElement t3 8
    mapToElements div10 t3 [1,9,3,8]
    div10 <$> t3
    

    Output

    True
    False
    Just 88
    Nothing
    Just 22
    Nothing
    [Just 8,Nothing,Just 2,Nothing]
    Node 6 4 (Node 3 9 (Node 1 8 Nil Nil) (Node 1 2 Nil Nil)) (Node 2 7 (Node 1 3 Nil Nil) Nil)
    
  • Information
    Author
    Jordi Petit, Gerard Escudero
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell