3

ネストされたデータ型 Bush を定義しました。

data Bush a = BEmpty | BCons a (Bush(Bush a))

ここで、Bushes に equal 関数を定義しようとしました。

eqB :: Eq a => Bush a -> Bush a -> Bool
eqB BEmpty BEmpty = True
eqB BEmpty _ = False
eqB _ BEmpty = False
eqB (BCons x bbush1) (BCons y bbush2) = x == y -- && ....

Bush(Bush) 問題は、関数 eqB' over を定義できる再帰呼び出しですが、Bush(Bush)eq onBush(Bush(Bush))などを処理する必要があることです。

この問題を解決する方法はありますか?

4

2 に答える 2

9

Bushは「非正規」または「非均一」データ型です。つまり、再帰的な場合、指定された型引数と同じ型引数を使用しません。これらの理由を説明するのは難しい場合がありますが、この場合、答えは思ったより簡単です。

data Bush a = BEmpty | BCons a (Bush (Bush a))

instance Eq a => Eq (Bush a) where
    BEmpty == BEmpty = True
    BCons x xs == BCons y ys = x == y && xs == ys
    _ == _ = False

それでおしまい！(==)自分自身を再帰的に呼び出すだけで、完了です。

しかし、ちょっと待ってください。ここで少し汚いトリックを使っています。Eq型クラス メカニズムを使用しています。

型クラスがまったくない場合、どうすればよいでしょうか? Eq a =>型クラスがなければ、そもそも制約を使用できませんでした。代わりに、明示的な比較関数を渡す場合があります:: a -> a -> Bool。それを念頭に置いて、非常によく似たコードを書くことができます。

eqBush :: (a -> a -> Bool) -> Bush a -> Bush a -> Bool
eqBush _ BEmpty BEmpty = True
eqBush eqA (BCons x xs) (BCons y ys) = eqA x y && eqBush (eqBush eqA) xs ys
eqBush _ _ _ = False

Bush a各再帰呼び出しでは、取得したのと同じ比較関数を渡しているわけではありません。sではなく sを比較する比較関数を渡していますa! これは、より明示的であることを除いて、型クラスで発生するのと実際には同じことです。再帰呼び出しの構造がデータ型定義の構造と同じであることに注意してBush (Bush a)くださいeqBush (eqBush eqA)。

この型に対する他の再帰的な定義でも同じことが起こります。これは便利なものです（これは本当にのfmapためのものです）：Bush

mapBush :: (a -> b) -> Bush a -> Bush b
mapBush _ BEmpty = BEmpty
mapBush f (BCons x xs) = BCons (f x) (mapBush (mapBush f) xs)

sumBushこれにより、次のような関数を簡単に記述できます。

sumBush :: Bush Int -> Int
sumBush BEmpty = 0
sumBush (BCons x xs) = x + sumBush (mapBush sumBush xs)

この種の再帰は多相再帰と呼ばれます。これは、多相関数が呼び出された型とは異なる型で自分自身を呼び出すためです。ポリモーフィック再帰は、理解するのが難しい場合があります。実際、その型推論は (一般的に) 決定不可能であるため、(一般的に) 独自の型シグネチャを作成する必要があります。より自然に。Bush感触をつかむために、他の関数をいくつか書いてみてください。

以下は、いくつかのコードを書いてみるための他のいくつかの非正規データ型です。

  • data Tree a = Leaf a | Branch (Tree (a,a))-- 完全な二分木。

  • dataFunLista b = Done b | More a (FunList a (a -> b))-- s のリストaと、正確にその数の s を取り、 aaを返す関数b(これはTraversalsに関連しています)。

于 2012-12-04T12:34:04.810 に答える
0

たとえば、Bush Int 内のすべての Int オカレンスの合計

sum:: Bush Int -> Int
sum BEmpty = 0
sum (BCons i BEmpty) = i
sum (BCons i bbush) = i + sum' bbush

bbush を処理する関数 sum' を作成できます。

sum':: Bush (Bush Int) -> Int
sum' BEmpty = 0
sum' (BCons bush bbbush) = sum bush -- + sum'' bbbush

エンディングはありません...

于 2012-12-04T11:43:56.257 に答える