Haskell - Arbres Foldables P76865

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.