-11 
data BTree a = Empty | Node (BTree a) a (BTree a) -- This is a node-labelled binary tree

誰かが次の Haskell 関数について説明してくれませんか?

  1. labels :: BTree a -> [a]

    labels Empty = []
labels (Node left label right) = labels left ++ [label] ++ labels right

  2. reflect :: BTree a -> BTree a

    reflect Empty = Empty
reflect (Node left label right) = Node (reflect left) label (reflect right)
4

1 に答える 1

5

最初に：いくつかのフォーマット。これは、このコードが通常Haskellでフォーマットされる方法です。

data BTree a = Empty 
             | Node (BTree a) a (BTree a)

labels :: BTree a -> [a]
labels Empty                   = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right

reflect :: BTree a -> BTree a
reflect Empty                   = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right)

（ヒント：コードを4スペースインデントすると、構文が正しく強調表示されます）。それでは、それを見ていきましょう。

data BTree a = Empty 
             | Node (BTree a) a (BTree a)

新しい「パラメトリック」データ型を定義します。型パラメータである小さいため、パラメトリックと呼ばれaます。これは、、、、など、a他のタイプに置き換えることができることを意味します。C++のテンプレートまたはJavaのジェネリックを考えてください。およびは、データ型のコンストラクターと呼ばれます。aは、または（それが象徴するもの）のいずれかであり、 anと別のを含むaを含みます。データ型（）が独自の定義に表示されるため、定義は再帰的です。IntDoubleStringEmptyNodeBTree aEmpty|NodeBTree aaBTree aBTree a

labels :: BTree a -> [a]
labels Empty                   = [] 
labels (Node left label right) = labels left ++ [label] ++ labels right

labelsツリーに含まれるすべての値を収集します。a最初の行は型宣言です。ノード（ ）を持つ二分木を取り、それをs（ ）のBTree aリストにマップします。タイプだけでも、何が起こっているのかについての良いアイデアがすでに得られます。a[a]

次の2行は、いわゆるパターン一致です。これらはcase他の言語のステートメントに似ています。さまざまな可能性を区別してから、適切なケースを選択します（ただし、はるかに強力です）。それらがを持っている2つのコンストラクターに正確に対応する方法に注意する必要がBTree aあります。ノードにいる場合はEmpty、空のリスト（）を返すだけ[]です。それ以外の場合は、次の行に進み、、、、、およびにバインドするanとaNodeが必要なaがあります。と呼んだかもしれませんが、これらは直感的です。BTree aaBTree aleftlabelrightleftlabelright

今度はタイプでleftあるため、両方を呼び出して、 sのリストを返すことを期待できます。したがって、ラベルは、その定義でそれ自体を呼び出すため、再帰的でもあります。これはHaskellでよく使われている非常に強力なテクニックです。次に、から取得したリストを連結します。リストには現在のラベル（）のみが含まれ、次にから取得したリストが連結されます。したがって、左側のサブツリーのラベルを現在のラベルおよび右側のサブツリーのラベルと結合し、すべてをリストに入れると効果的に結論付けることができます。rightBTree alabelsa[a]labelslabels left[label]labels right

reflect :: BTree a -> BTree a
reflect Empty                   = Empty 
reflect (Node left label right) = Node (reflect left) label (reflect right)

labelsリストではなくラベルのツリーを返すことを除いて、とほぼ同じように機能します。事実上、これは何もしません。少し高価な恒等関数です。しかし、それはもっと強力なもののテンプレートです。たとえば、別の関数を簡単に渡しreflectて、その各要素に適用できます。

于 2013-01-08T12:26:32.967 に答える