3

私のツリーの定義は次のとおりです。

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

配列の 3 番目ごとの要素 (1 番目、4 番目、7 番目、...) のみを選択するフィルター関数を作成したいと考えています。例として、私のツリーが次のようになっているとします。

Node 
    (Node 
        (Node 
            (Leaf 'a') 
            (Leaf 'b')) 
        (Leaf 'c'))
    (Node 
        (Node 
            (Leaf 'd') 
            (Leaf 'e')) 
        (Leaf 'f'))

次に、フィルター関数は次のような新しいツリーになります。

Node (Leaf 'a') (Leaf 'd')
4

1 に答える 1

4

これがあなたのためのゲームプランです。

  1. ツリーの各要素に関数を適用する関数を作成します。 

    mapTree :: (a -> b) -> Tree a -> Tree b

    (おまけ:インスタンスを作成Treeし、 の代わりに使用)FunctorfmapmapTree

  2. ツリーの要素を左から右への順序でラベル付けする関数を作成します。

    labelTree :: Tree a -> Tree (Integer, a)

    (ヒント: 「現在のラベル」を受け取り、新しいラベルとともにラベル付きツリーを返す補助関数が必要になります。つまり:: Integer -> Tree a -> (Tree (Integer, a), Integer)、この関数の分岐ケースは次のようになります。

    aux n (Branch l r) = 
    let (l', n')  = aux n l
        (r', n'') = aux n' r in
    (Branch l' r', n'')

    このコードを注意深く読んでから、ケースを思いつくことができるかどうかを確認してくださいLeaf)

    (おまけ:Stateモナドを使ってやってみよう)

  3. 条件を満たさないツリーの要素を削除する関数を作成します。

    filterTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

    Maybe (Tree a)単なる a ではなくa を返すことに注意してください。これは、条件に一致する要素がなく、型が空のツリーを許可しないTree a場合に何かを返す必要があるためです。Treea を返すことで、Maybe (Tree a)この関数を再帰的に書くのが非常に簡単になることもあります。

  4. これらの関数を組み合わせて、探している関数を取得します。つまり、3 で割り切れるラベルを持つ要素のみを除外します。

このように分解することの良い点は、特定の問題を解決することに加えて、Tree型を操作するための一般的に便利なツールをいくつか自分で作成したことです。マップとフィルターは、データ構造を実装するときに表示される非常に一般的な関数です。

上級:のStateモナド ボーナス実装は、 「トラバーサル」labelTreeと呼ばれる別の一般的なタイプの関数の特定のケースです 。

traverse :: (Applicative f) => (a -> f b) -> Tree a -> f (Tree b)

これはマップに似ていますが、各要素で発生する可能性のある「効果」も組み合わせています。あなたがそれを実装し、それを使って書くことができれば、スーパーダブルプラスボーナスlabelTree.

于 2013-06-12T05:10:02.183 に答える