1

この関数によって返される値の意味は何ですか? 必要に応じて図を使用して説明できます 

data Tree a = Empty_Tree | Node {element :: a, left_tree,right_tree :: Tree a}
gurgle :: Tree a -> Tree a -> Bool
gurgle tree_a tree_b = case (tree_a, tree_b) of
      (Empty_Tree , Empty_Tree ) -> True
      (Empty_Tree , _ ) -> False
      (_ , Empty_Tree ) -> False
      (Node _ left_a right_a, Node _ left_b right_b) -> gurgle left_a right_b
                                                        && gurgle right_a left_b
4

1 に答える 1

6

描いてみましょう。まず、空のツリーに小さな円を使用し、ノードのデータに円を使用します。サブツリーには 2 つの枝があります。leftそしてrightそれ自体も木になります。

単純な木の例

では、コードを 1 行ずつ取り出して、case ステートメントを最上位のパターン マッチングに展開しましょう。

function x y = case (x,y) of
    (0,1) -> this
    (1,10) -> that

書くことができます

function 0 1 = this
function 1 10 = that

ぐるぐるEmpty_Tree Empty_Tree = True

規範事例

ここで学ぶべきことはたくさんあります - 両方とも空ならイエスです。わかった。

ぐるぐるEmpty_Tree _ = False

これは、次のようなものを取得することを意味します

empty,notempty は False を返します

False2番目の引数が何であれ、それは与えるからです。2 番目の引数が最後の行にあるケースは既に排除されているEmpty_Treeため、ここで False を指定するには、2 番目の引数が空でない必要があります。

次の行は非常によく似ていますが、逆になっています。

gurgle _ Empty_Tree = False

繰り返しますが、このようなもの

空でない、空の場合は false

いいえの答えを得ています。この 2 行を読むと、2 つの木の形に同じものがあることが確認されているのではないかと疑い始めます。

再帰的なケース

ぐるぐる xy = ぐるぐる (left_tree x) (right_tree y) && ぐるぐる (right_tree x) (left_tree y)

これは最も興味深いものです。それが行っているスワップサイドに注意してください。両方のサブツリーが同じであることを確認するだけでなく、右と左を比較しています。

一致しない

また、ノードの値を無視していることにも注意してください。そのため、この例では数字を削除しました。

それを真にするために何が必要ですか？

それを実現するには、一方の左側の形状を他方の右側の形状と一致させる必要があります。

鏡映された木

あなたのポイントは何ですか？

再帰的なケースでは、一方の左が他方の右と一致する必要があります。値を無視すると、ツリーは互いに鏡像である必要があります。

パターンマッチで何が起こっているのですか？

元の再帰ケースは言った

   (Node _ left_a right_a, Node _ left_b right_b) -> gurgle left_a right_b
                                                    && gurgle right_a left_b

上記の図と一致するように、そのコードに色を付けてみましょう。

色分けされたコード

left_a左側の名前などは特別なことを意味するものではなく、ツリーの一部を参照するためにあるだけなので、色を付けることは何が起こっているかを視覚的に示す良い手がかりになります。

どのビット？

ノード _ left_a right_a

これは Node の定義と一致させるためにあります:

データ ツリー a = Empty_Tree | ノード {要素 :: a, left_tree,right_tree :: 木 a}

最初の (灰色の) ビットは要素です。elementツリー ノードから値への関数になりました。

2 番目 (薄い茶色) のビットは、左のサブツリーですleft_tree。大規模で複雑な場合もあれば、Empty_Tree. (どのツリーでもかまいません。)

3 番目 (薄いオレンジ色) のビットは、右側のサブツリー ですright_tree。それらは、次のように私の図と一致します。

木

色付きのボックスには詳細を入れていません。大小を問わず、どんな木でもかまいません。

元のコードでこれを左側に配置すると

色分けされたコード

left-tree関数と関数を使用するのではなく、サブツリーを直接参照できるように、サブツリーに名前を付けていましたright_tree。

于 2013-06-10T00:05:27.207 に答える