Türlü örneklerin türleri için tür sınırlamaları * -> *

Question

Heap türünde * -> * türünde bir kurucu olan Heap a türüne sahip olduğumu varsayalım. Yığın üzerindeki birçok temel işlem, a türünün Ord tür sınıfının bir örneği olmasını gerektirir.

data Heap a = ... 

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

Ben (findMin ve deleteMin fonksiyonları aracılığıyla ifade etmek kolay olacaktır) en kısa sürede a tür parametresi Ord tip sınıfının bir örneğidir olarak Foldable tipi sınıfının bir örneği olarak benim Heap türü bildirmek istiyorum.

biz Show gibi nazik * tipini gerektiren tip sınıfları konusunu ele alırken ilişkinin Bu tür easely ifade edilebilir:

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

Ama elimdeki sorunları bildirimiyle Foldable ait:

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

Bu örnek beyanda a tip parametresi üzerinde kısıtlama koymak mümkün mü?

Answer 1

Genel olarak, hayır, yapıcı türünün kendisine verildiği zaman, uygulandığı türleri kısıtlama yolu yoktur. Çoğunlukla bu iyi bir şeydir, çünkü Functor örnekleri, güzel ve öngörülebilir davranışları güzel ve öngörülebilir tutmaya yardımcı olan, eleman türleriyle ilgili gerçekten agnostiktir.

Bunun yerine bazen bir sıkıntıdır ve en yaygın örnek, güzel, iyi huylu bir örnek olabilecek sıralı bir veri yapısı için Ord kısıtlamasına gereksinim duyar.

Kısıtlama türlerini içeren bazı deneysel teknikler vardır, ancak özel durumunuzda zaten geçerli bir çözüm var. Foldable tanımına bakarsanız, yalnızca foldMap veya foldr'un uygulanması gerektiğini söylüyor, dolayısıyla bunları dikkate alacağız. türlerini Not: Her iki durumda da

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

, bir Foldable örnekle türü yalnızca işlevine argüman olarak bir kez görünür. Bu nedenle, bir Ord kısıtlaması ile use GADTs edebilirsiniz:

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

Bunu yaparak, size Heap değeri, hatta boş bir yığın oluşturmak her zaman bir Ord örneğini gerekir; ancak , değerini Heap değeri aldığınızda, Ord örneğini örneğini Foldable örneğinin içinde bile kapsam içine getirecektir! Bu diğer birçok durumlarda yardımcı olmadığını

Not:

İşte

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

biz a bir Ord örneğini alabilirsiniz, ama biz de mümkün değildir ki, b tane gerekiyordu.

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

İşte biz de bir Ord örneğini sağlamanız gerekir.

Answer 2

Hackage'da keys kütüphanesine göz atın. FoldableWithKey tip sınıfının ihtiyacınız olan şey olup olmadığını kontrol edin.