Haskell - Arbres Foldables P76865


Statement
 

pdf   zip

html

En Haskell, la classe estàndard Foldable és l’encarregada de permetre l’ús dels folds sobre dades estructurades per tal d’obtenir-ne un agregat. Per exemple, les llistes són instàncies de Foldable, i la funció sum és definida a la classe Foldable.

La classe Foldable es defineix (essencialment) d’aquesta forma:

class Foldable t where foldr :: (a -> b -> b) -> b -> t a -> b foldl :: (b -> a -> b) -> b -> t a -> b null :: t a -> Bool length :: t a -> Int elem :: Eq a => a -> t a -> Bool maximum :: Ord a => t a -> a minimum :: Ord a => t a -> a sum :: Num a => t a -> a product :: Num a => t a -> a

Per instanciar Foldable només cal definir foldr, ja que totes les altres operacions tenen una definició per defecte que l’utilitza.

L’objectiu d’aquest exercici és fer que el tipus dels arbres binaris sigui una intància de la classe Foldable. Considereu aquest tipus pels arbres binaris:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

Es demana:

  1. Feu que Tree sigui una instància de Foldable. Per fer-ho, implementeu la funció foldr aplicant una funció als elements de l’arbre tot seguint un recorregut en preordre.
  2. Definiu una funció avg :: Tree Int -> Double per calcular la mitjana dels elements d’un arbre d’enters no buit. Useu fromIntegral per convertir d’enter a real.
  3. Definiu una funció cat :: Tree String -> String per concatenar amb espais tots els nodes d’un arbre de textos.

A l’hora de corregir es tindrà en compte la correcció, senzillesa, elegància i consició de la solució proposada.

Public test cases

  • Input

    maximum $ Node 'a' (Node 'c' Empty Empty) (Node 'b' Empty Empty)
avg $ Node 10 (Node 20 Empty Empty) (Node 30 Empty Empty)
cat $ Node "mi" (Node "mama" Empty Empty) (Node "me" (Node "mima" Empty Empty) Empty)

    Output

    'c'
20.0
"mi mama me mima"
    • Information
    Author
    Gerard Escudero, Jordi Petit
    Language
    Catalan
    Official solutions
    Haskell
    User solutions
    Haskell