6

クライアントから「実際の」注文を隠す Bag コンテナーが必要です。

また、完全にポリモーフィックである必要があります。つまり、要素の型に対する制約は必要ありません。

少なくとも 3 つのバッグの実装が見つかりました: Bagmodule from ghcpackage、Data.BagfrombagおよびMath.Combinatorics.Multisetfrom multiset-comb。

ただし、それらにはすべて、実装の詳細またはバッグ構築の順序に依存する要素の内部順序を公開する操作がありますtoList。fold*

toList少なくとも type では不可能Bag a -> [a]です。ただし、折り畳みによって常に順序が明らかになるとは限りません。

たとえば、fold (+) 0露出しません。

問題は、折りたたみインターフェースをどのように設計すればよいかということです。a -> a -> aフォールディング機能の安全性に必要十分条件はありますか？は順序を公開していないためfmap、 で折りたたむと汎用性が失われa -> b -> bますか?

私は可換モノイドについて考えています - それらは十分に思えますが、結合性と恒等要素が必要かどうかはわかりません。

4

1 に答える 1

6

バッグが空になる可能性がある場合は、おそらくIDが必要です。その場合は何かを返却する必要があり、折り畳みを準同型にしたい場合（いくつかのバッグを折りたたんだ結果を組み合わせると、バッグを組み合わせると、これは非常に自然な特性です）、アイデンティティ要素である必要があります。

同様に、結合性は良い考えです。次のようなタイプと操作があるとします。

data T a = Zero | One a | Two (T a) (T a)
  deriving (Eq, Ord, Show)

(+-+) :: Ord a => T a -> T a -> T a
Zero +-+ x = x
x +-+ Zero = x
a +-+ b = Two (min a b) (max a b)

明らか(+-+)に可換であり、アイデンティティを持っていますが、結合的ではありません。次に、バッグをリストとして実装するとします。

newtype Bag a = Bag [a]

-- pre-condition: f is commutative and z is an identity for it
foldBag :: (a -> a -> a) -> a -> Bag a -> a
foldBag f z (Bag xs) = foldr f z xs

foldNonAssoc :: (Ord a) => Bag (T a) -> T a
foldNonAssoc = foldBag (+-+) Zero

記載された前提条件を要求した場合でも、を使用して、に折りたたむとに折りたたむをfoldNonAssoc区別できます（すべての構造が保持されるわけではありませんが、長いリストではリスト全体を取得します）最後の2つの要素の順序を除いて、並べ替えます）。Bag [One 1,One 2,One 3]Two (One 1) (Two (One 2) (One 3))Bag [One 3,One 2,One 1]Two (One 3) (Two (One 1) (One 2))

先験的に、すべてのアイテムを操作と組み合わせると、のようなアプリケーションのツリーができますa +-+ (b +-+ (c +-+ d))。可換性により、ある程度の再配置が可能になりますが、何を実行しても、c常に。と組み合わされdます。したがって、それをと同じにしたい場合は(a +-+ c) +-+ (b +-+ d)、実際には結合性も必要です。

于 2012-09-05T13:17:09.580 に答える