ツリーのミラーリング

Question

割り当てはツリーをミラーリングすることです（すべてのレベルで最も左の子が右端になります）。だから、

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) 

私は一例で、このコードを実行します：

データ構造：

import Data.List 

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

私がこれまでに出ているものを

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

関数は私にを返すは左端の葉にくっついていることを意味します。私のコードで判断すると、与えられたノードの子の子孫をy:ysに渡していないので、論理的であるようです。どういうわけか、与えられたノードの最初の子のすべての子を逆転させることができなければならず、同じ関数の末尾にを渡す必要があります。どんなに頑張っても、私はこれを達成できず、論理的思考の限界にぶつかったように見えます。

Documentation for reverse function

Answer 1

私は最初の子供と残りの子供のような小さな言葉で考えないでください。代わりに、全体の画像を見てみてください。

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

我々は再帰的にこれについて考える場合、私たちは、ツリーをミラーリングすることができますことを観察することができます子供の順序を逆に

1. 。
2. 子ども自身を再帰的にミラーリングします。

あなたはすでにreverseの使い方を知っています。リスト内のすべての要素に関数fを適用するには、map fを使用できます。これらを一緒に使って自分で解決できるかどうかを試してみてください。

スポイラー：

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

Answer 2

あなたが正しく指摘したように、あなたはあなたのmirror関数内ですべてysを使用していないので、結果はおそらく右することはできません。

この問題を解決するには、Roseの再帰的構造とミラーリングがそれにどのような影響を与えるかを考えてください。

つまり、ツリーを鏡映するには、その子孫の順序を逆にしながら、そのルートを維持し、それぞれの子を（再帰的に）反映させる必要があります。

これが明らかな場合は、これらの単語をハスケルコードに翻訳するだけです。

自問：

1. どのように私は、子供たちのそれぞれに関数を適用し、リスト内の結果を収集することができますか？

2. 逆の順序で1を行うにはどうすればよいですか？

3. 本当に空のリストケースを別に処理する必要がありますか？