Haskell - Arbres amb talla P58738


Statement
 

pdf   zip

html

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