Haskell - Arbres Foldables P76865

Statement

thehtml

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:

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.
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.
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