9

私は Haskell にはかなり慣れていません (まだモナドを完全に理解することに取り組んでいます)。ツリーのような構造を持つ問題があります

type Tree = [DataA]

data DataA =  DataA1 [DataB] 
            | DataA2 String 
            | DataA3 String [DataA]
               deriving Show

data DataB =  DataB1 [DataA] 
            | DataB2 String 
            | DataB3 String [DataB]
               deriving Show

私がやりたいことは、これをトラバースして、フィルターを使用して新しいツリーを生成できるようにすることです。たとえば、ツリー内のすべての DataB2 を「foo」に変更したい場合があります。

ツリーが同じデータ セクションにあり、コンストラクターが似ている場合の例を見てきました。

Python の世界では、リストをたどり、必要なものに一致させ、値を置き換えるだけでした。

Haskell では、ツリーをコピーできるようにする必要があると推測していますが、コンストラクターやさまざまなデータ型に埋め込まれたリストをどのように処理しますか?

4

4 に答える 4

11

これには汎用プログラミングを使用できます。

そのような汎用プログラミング ライブラリの 1 つは Scrap Your Boilerplate と呼ばれます。モジュールの最上部で、次のように記述して Scrap Your Boilerplate を有効にします。

{-# LANGUAGE DeriveDataTypeable #-}

モジュールをインポートしますData.Generics。次に、データ型のShow派生TypeableとDataインスタンスも作成します。

これで、リクエストした関数を次のように記述できます。

toFoo :: Data a => a -> a
toFoo = everywhere (mkT step)
  where
    step (DataA2 _)  = DataA2 "foo"
    step x           = x

この作業を行うために必要な作業はこれだけです。たとえば、 を呼び出すtoFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []]と、答えは[DataA1 [],DataA2 "foo",DataA3 "yo" []]です。

お役に立てれば！

于 2010-02-26T10:55:39.040 に答える
2

あなたの質問に対する一般的な答えはわかりません。データ型は非常に工夫されており、おそらくフィルターではなくフォールドを実装することを選択します。ただし、ここに4つの位置すべての文字列を更新できるいくつかのフィルター関数があります。コードをコンパイラーに通したので、タイプチェックを行いましたが、実行していません。

type SFilter = String -> String

-- to filter a tree, say how A2, A3, B2, and B3 should be changed

type Filter tree = SFilter -> SFilter -> SFilter -> SFilter -> (tree -> tree)

afilter :: Filter DataA
bfilter :: Filter DataB
tfilter :: Filter Tree

tfilter a2 a3 b2 b3 = map (afilter a2 a3 b2 b3)
afilter a2 a3 b2 b3 = fil
  where fil (DataA1 bs)   = DataA1 $ map (bfilter a2 a3 b2 b3) bs
        fil (DataA2 s)    = DataA2 (a2 s)
        fil (DataA3 s as) = DataA3 (a3 s) (map fil as)

bfilter a2 a3 b2 b3 = fil
  where fil (DataB1 as)   = DataB1 $ map (afilter a2 a3 b2 b3) as
        fil (DataB2 s)    = DataB2 (b2 s)
        fil (DataB3 s bs) = DataB3 (b3 s) (map fil bs)
于 2010-02-26T00:41:12.077 に答える
2

データ構造全体をトラバースし、あちこちでいくつかの項目を変更したいとします。これは通常、データ構造をパラメーターとして取り、構造の新しく変更されたバージョンを返す関数によって行われます。

入力のすべてのケースに対して、この関数は、返される新しい値がどのように見えるかを定義します。

Treea (単なる値のリスト)を変更する基本的な関数は、変更DataAされた値の新しいリストを返すだけでよいでしょう。これらの値の変更を関数に任せるmodifyAと、主な変更関数は次のようになります。

-- # function to change a |Tree|
mutate :: Tree -> Tree
mutate as = map mutateA as
     -- # (The |map| function applies the |mutateA| function to every
     -- #  element of |as|, creating a list of all the return values)

次に、mutateA可能なすべての値を変更するように関数を定義する必要があります。値を処理する関数をDataA伴うのが最善です。mutateBDataB

これらの関数は、考えられるさまざまな値のケースを調べて、適切な新しい値を返します。

-- # function to change |DataA| items
mutateA :: DataA -> DataA
     -- # A |DataA1| is a |DataA1| with modified values
mutateA (DataA1 bs)   = DataA1 (map mutateB bs)
     -- # A |DataA3| is a |DataA3| with modified values
mutateA (DataA3 s as) = DataA3 s (map mutateA as)
     -- # In the remaining case(s) the value stays the same
mutateA d             = d

-- # function to change |DataB| items
mutateB :: DataB -> DataB
mutateB (DataB1 as) = DataB1 (map mutateA as)
mutateB (DataB3 s bs) = DataB3 s (map mutateB bs)
     -- # Here comes a real change
mutateB (DataB2 _)  = DataB2 "foo"

このようにして、ツリー内のすべての要素に対して新しい要素が計算さDataB2 れ、ツリー内のすべての値が「foo」に置き換えられます。

ウォークスルーする必要がある値のリストを含む 5 つの異なるケースがあるため、比較的冗長ですが、これは Haskell に固有のものではありません。命令型言語では、通常、 への 5 つの呼び出しの代わりに 5 つの for ループを使用しますmap。

この「オーバーヘッド」を減らすために、データ構造を単純化できるかもしれません。もちろん、これは実際のユースケースに依存しますが、たとえば、Data2ケースは必要ないかもしれません: と の間に違いはDataA2 "abc"ありDataA3 "abc" []ますか?

于 2010-02-26T00:54:58.630 に答える
0

相互に再帰的なデータ型を操作するには、multirecライブラリを参照してください。私はそれを使用していませんが、あなたが説明したことから、あなたが取り組んでいる種類の問題を正確に狙っているように思えます. ここでの他の回答が示唆しているように、汎用プログラミングを使用しますが、すべてを自分で実装する時間を節約できます。

于 2010-02-26T15:03:04.167 に答える