Haskell Binary Tree Fonction (Carte)

Question

Comment puis-je définir une fonction Haskell qui applique une fonction à chaque valeur dans un arbre binaire? Donc, je sais qu'il est similaire à la fonction map - et que son type serait:

mapT :: (a -> b) -> Tree a -> Tree b 

Mais thats à son sujet ...

Answer 1

Je vais faire semblant que c'est des devoirs et non donner tous la réponse. Si je me trompe, mes excuses.

probablement votre type Tree ressemble à quelque chose comme ceci:

data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode 

Il y a deux cas ici, et vous aurez besoin d'écrire une implémentation mapT pour chacun d'eux:

• Un noeud interne, TreeNode, qui porte une valeur de type a et a un gauche et un droit de l'enfant. Que doit-on faire dans ce cas?
• Un noeud terminal, EmptyNode. Que doit-on faire dans ce cas?

Answer 2

Question intéressante si l'entrée et la sortie sont censés être arbres binaires triés. Si vous parcourez simplement naïvement l'arbre et appliquez la fonction, l'arborescence de sortie ne peut plus être triée. Par exemple, considérer si la fonction est non-linéaire, comme

f(x) = x * x - 3 * x + 2 

Si l'entrée a {1, 2, 3, 4} alors la sortie aura {2, 0, 0, 2}. L'arbre de sortie devrait-il contenir seulement 0 et 2?

Si oui, vous devrez peut-être construire itérativement l'arbre de sortie que vous dépouillez vers le bas et traiter l'arbre d'entrée.

Answer 3

Le format de base de la fonction de carte s'applique à la fois. Regardons la définition de la fonction de carte pour les listes:

map f (x:xs) = f x : map f xs 
map _ []  = [] 

On peut généraliser cette façon:

1. Vous prenez la première valeur de la structure de données
2. Appliquer la fonction à elle
3. Appelez récursivement votre fonction de carte avec le reste de la structure de données
4. Transmettez la valeur modifiée et l'appel récursif dans le constructeur pour votre type.
5. Lorsque vous arrivez à la fin, arrêtez récursion

Tout ce que vous avez vraiment besoin est de regarder votre constructeur et la fonction de carte devrait tomber en place.

Answer 4

Vous pouvez déclarer une instance de la classe Functor. C'est une classe standard pour les types de données qui permettent de mapper une fonction.S'il vous plaît noter la similitude du type de fmap est à votre type de » mapT:

class Functor f where 
    fmap :: (a -> b) -> f a -> f b 

Supposons que votre arbre est défini comme

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

Ensuite, vous pouvez déclarer une instance de Functor cette façon:

instance Functor Tree where 
    fmap f (Node l r) = Node (fmap f l) (fmap f r) 
    fmap f (Leaf x) = Leaf (f x) 

Voici comment vous pouvez l'utiliser:

main = do 
    let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) 
    let f = show . (2^) 
    putStrLn $ "Old Tree: " ++ (show t) 
    putStrLn $ "New Tree: " ++ (show . fmap f $ t) 

Sortie:

Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) 
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8") 

Vous pouvez également définir pour des raisons pratiques:

mapT = fmap 

Sûrement, vous pouvez le faire sans classes de type, mais il rend le code plus lisible pour les autres si vous utiliser des fonctions standard (tout le monde connaît le comportement habituel de fmap).