haskell - 镜像一棵树

Question

任务是镜像一棵树(所以在每一层，最左边的 child 变成最右边的 child 等等)。

数据结构:

import Data.List

data Rose a = Node a [Rose a]
         deriving (Eq, Show)

到目前为止我的想法:

mirror :: Rose a -> Rose a
mirror (Node x []) = Node x []
mirror (Node x (y:ys)) = mirror (myReverse y)

--reverses given node children
myReverse :: Rose a -> Rose a
myReverse (Node x y) = Node x (reverse y)

所以当我用示例运行这段代码时:

Main> mirror (Node 1 [Node 11 [Node 111 [], Node 112[]], Node 12 [Node 121[]]])

该函数返回我 Node 112 [] 意味着它卡在最左边的叶子上。从我的代码来看，这似乎是合乎逻辑的，因为我没有在 y:ys 处传递给定节点子节点的尾部。不知何故，我必须能够反转给定节点 AND 的第一个 child 的所有 child ，并将尾部传递给相同的功能。无论我怎么努力，我都无法做到这一点，看来我已经达到了我的逻辑思维的极限。

Documentation for reverse function

Answer 1

我会避免像第一个 child 和其他 child 那样从小事上考虑它。相反，请尝试查看全貌。

                a                             a
             /     \                       /     \
            b       c        ===>         c       b
          / | \    / \                   / \    / | \
         d  e  f   g  h                 h   g  f  e  d

如果我们递归地考虑这一点，我们可以观察到我们可以通过以下方式镜像一棵树:

1. 颠倒 child 的顺序。
2. 递归地镜像 child 自己。

您已经知道如何使用 reverse。要将函数 f 应用于列表中的每个元素，您可以使用 map f。试试看能不能把这些结合起来自己解决。

剧透:

mirror (Node a children) = Node a (reverse $map mirror children)