16

Heap atypeがHeapkind の型コンストラクターであるとし* -> *ます。ヒープに対する多くの基本的な操作では、型が型クラスaのインスタンスである必要があります。Ord

data Heap a = ...

findMin :: Ord a => Heap a -> a
deleteMin :: Ord a => Heap a -> Heap a

型パラメーターが型クラスのインスタンスであるとすぐに、型を型クラスHeapのインスタンスとして宣言したいと思います ( and関数を介して簡単に表現できます)。FoldableaOrdfindMindeleteMin

*この種の関係は、次のような種類の型を必要とする型クラスを扱うときに簡単に表現できますShow。

instance Show a => Show (Heap a) where
    show h = ...

しかし、次の宣言に問題がありFoldableます:

instance Foldable Heap where
    -- Ouch, there is no `a` type parameter to put the constraint on!
    foldr f z h = ...

aこのようなインスタンス宣言で、型パラメータに制約をかけることはできますか?

4

2 に答える 2

18

一般に、いいえ、型コンストラクター自体にインスタンスが与えられた場合、それが適用される型を制約する方法はありません。Functorこれは、たとえばインスタンスが要素タイプについて真に不可知論的であることを保証するため、ほとんどの場合、これは良いことです。これにより、適切で予測可能な動作を適切で予測可能に保つことができます。

代わりに煩わしい場合もありますが、最も一般的な例はOrd、ソートされたデータ構造の制約が必要な場合です。それ以外の場合は、適切に動作するインスタンスになる可能性があります。

制約の種類のようなものを含むいくつかの実験的手法がありますが、特定のケースでは、すでに実行可能な解決策があります。の定義を見ると、実装する必要がある、または実装する必要がFoldableあると書かれているので、それらを検討します。タイプに注意してください：foldMapfoldr

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b

どちらの場合も、Foldableインスタンスを持つ型は、関数の引数として1回だけ表示されます。このため、 GADTをOrd制約付きで使用できます。

data Heap a where
    Heap :: (Ord a) => ...

これを行うことにより、値を作成するOrdときはいつでも、空のヒープであってもインスタンスが必要になります。ただし、値を受け取ると、その値のパターンマッチングにより、インスタンスがスコープ内に戻ります。インスタンス内であってもです。HeapHeapOrdFoldable

これは他の多くの状況では役に立たないことに注意してください。

fmap :: (Functor f) => (a -> b) -> f a -> f b

ここでは、のOrdインスタンスを取得できますが、のインスタンスaも必要になりますがb、これは不可能です。

return :: (Monad m) => a -> m a

ここでは、Ordインスタンスも提供する必要があります。

于 2012-09-19T16:41:22.437 に答える
0

keysHackageのライブラリを見てください。そのFoldableWithKey型クラスが必要なものかどうかを確認してください。

于 2012-09-19T22:26:28.833 に答える