映射在树中的列表

Question

我需要你的帮助来解决以下两个功能/问题:

1)

我必须替换树中的元素.树的分支可以具有任意数量的子分支,如下面的代码所示.

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)

我必须通过元素并改变它们.我的问题在最后一行.mapmtree函数接受(树a)但是分支可以有一个子分支列表,因此不可能编译上面的代码,因为它给出了错误.如何在分支的子列表上调用mapmtree函数？

这是我加载时得到的错误:

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)

第二个是处理将树变成列表的深度优先 这是我现在的代码,但是我被困住了,不知道如何进一步:

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)

还需要帮助以及如何实现它.与上面相同的问题,分支可以有很多子树,需要深入研究它们,先制作一个元素列表.

请在Haskell做一个初学者,所以不要生我的气.

谢谢

Answer 1

1)

首先,我注意到你所做的map f a虽然a是一个单一的值,而不是一个列表¹.所以,你应该做的f a不是map f a.

现在问你实际问的问题:

你是对的,它不起作用,因为它c是一个树列表,mapmtree只需要一棵树.所以你会怎么做？您应用于mapmtree树列表中的每个树,然后使用结果树列表作为新分支的树列表.你是怎样做的？map在列表中使用:

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

2)

如1)你map用来申请mtree2list每棵树c.结果将是列表².要将此列表列表转换为平面列表,您可以使用该concat功能.

¹当然,除非你正在呼叫mapmtree列表树.

²因为每个树都映射到列表mtree2list,map然后返回包含调用结果的列表mtree2list.