Cartographie du Liste dans un arbre

Question

j'ai besoin de votre aide pour résoudre les 2 fonctions/problèmes suivants:

1)

Je dois remplacer les éléments dans un arbre. La branche de l'arbre peut avoir n'importe quel nombre de sous-branches comme indiqué ci-dessous dans le code.

data Tree a = Leaf a | Branch a [(Tree a)] deriving (Show) 

mapmtree :: (a -> a) -> Tree a -> Tree a 
mapmtree f (Leaf a) = (f a) 
mapmtree f (Branch a c) = Branch (map f a) (mapmtree f c) 

Je dois me déplacer à travers les éléments et les changer. Mon problème est dans la dernière ligne. La fonction mapmtree accepte (Tree a) mais la branche peut avoir une liste de sous-branches donc il n'est pas possible de compiler le code ci-dessus car il donne des erreurs. Comment puis-je appeler la fonction mapmtree sur les sous-listes de la branche?

C'est l'erreur que je reçois quand je le charge:

Couldn't match expected type `Tree a' 
      against inferred type `[Tree a]' 
    In the second argument of `mapmtree', namely `c' 
    In the second argument of `Branch', namely `(mapmtree f c)' 
    In the expression: Branch (map f a) (mapmtree f c) 

2)

La deuxième traite de transformer un arbre en liste -première profondeur C'est le code j'ai maintenant mais je suis coincé et je ne sais pas comment aller plus loin:

data Tree a = Leaf a | Branch a [(Tree a)] deriving (Show) 

mtree2list :: Tree a -> [a] 
mtree2list (Leaf a) = [a] 
mtree2list (Branch a c) = a : (mtree2list c) 

Besoin d'aide aussi comment Mettre en œuvre. Le même problème que ci-dessus, la branche peut avoir de nombreux sous-arbres et doivent passer par eux profondeur d'abord pour faire une liste des éléments. S'il vous plaît suis un débutant total dans Haskell alors ne soyez pas en colère contre moi.

Merci

Answer 1

1)

Tout d'abord tout ce que je remarque que vous faites map f a bien a est une valeur unique, pas un list¹. Donc, vous devriez faire f a pas map f a.

maintenant au problème que vous avez réellement posé des questions sur:

Vous avez raison que cela ne fonctionne pas parce que c une liste des arbres et mapmtree ne veut un seul arbre. Donc que fais-tu? Vous appliquez mapmtree à chaque arbre de la liste des arbres, puis utilisez la liste des arbres résultants comme liste d'arbres pour la nouvelle branche. Comment tu fais ça? En utilisant map sur la liste:

mapmtree f (Branch a c) = Branch (f a) (map (mapmtree f) c) 

2)

Comme dans 1) vous utilisez map pour appliquer mtree2list à chaque arbre c. Le résultat sera une liste de listes². Pour transformer cette liste de listes en une liste plate, vous pouvez utiliser la fonction concat, qui fait exactement cela.

---

À moins que vous ¹Ces appeler mapmtree sur un arbre de listes, bien sûr.

² Parce que chaque arbre est mis en correspondance avec une liste par mtree2list et map renvoie alors une liste contenant les résultats de l'appel mtree2list.

Answer 2

De plus, la première partie est erronée car votre fonction (a -> a) ne vous donne pas le type d'arbre que vous voulez. Vous devez changer cela en

mapmtree f (Leaf a) = Leaf (f a)