Haskell Tür Bağlamı, işlevler için gerekli bildirimler için gerekli

Question

Oluşturduğum veri türü için örnek bildirimi yaparken bir tür bağlam kullanmıştım.

data Set a = Insert a (Set a) | EmptySet 

instance (Show a) => Show (Set a) where 
    show x = "{" ++ show' x ++ "}" where 
     show' (Insert x EmptySet) = show x 
     show' (Insert x xs) = show x ++ ", " ++ show' xs 

instance Eq a => Eq (Set a) where 
    (Insert x xs) == (Insert y ys) = (x == y) && (xs == ys) 

Yani şimdi, ben o kadar olduğu gibi, benim Seti türü kullanmak tanımlayan fonksiyonların tümüne Denklem tipi bağlam eklemek zorunda, yoksa bir tür hatayı alıyorum:

memberSet::Eq a =>a->Set a->Bool 
memberSet _ EmptySet = False 
memberSet x (Insert y ys) 
    | x == y = True 
    | otherwise = memberSet x ys 

subSet::Eq a=>Set a->Set a->Bool 
subSet EmptySet _ = True 
subSet (Insert a as) bs 
    | memberSet a bs = subSet as bs 
    | otherwise = False 

hatası Görünüşe göre:

No instance for (Eq a) 
     arising from a use of `==' 
    In the expression: (x == y) 
    In a stmt of a pattern guard for 
       an equation for `memberSet': 
     (x == y) 
    In an equation for `memberSet': 
     memberSet x (Insert y ys) 
      | (x == y) = True 
      | otherwise = memberSet x ys 
Failed, modules loaded: none. 

Bu ne anlama geliyor? Neden bu hatayı alıyorum? Örnek beyanı verdikten sonra, Haskell, "memberSet" ve "subSet" işlevlerimde "==" ile karşılaştırılan şeylerin otomatik olarak "Eq?" Örneklerini kontrol edeceğini otomatik olarak doğrulayabileceğimi düşündüm. netlik için

Düzenleme:

Sorunum tip bağlamları "memberSet" ve neden gerekli olduğunu anlamak kalmamasıdır "alt küme". Onları böyle kaldırırsam, derleme yapmaz. senin örnek beyanı diyor ne

memberSet::a->Set a->Bool 
    memberSet _ EmptySet = False 
    memberSet x (Insert y ys) 
     | x == y = True 
     | otherwise = memberSet x ys 

    subSet::Set a->Set a->Bool 
    subSet EmptySet _ = True 
    subSet (Insert a as) bs 
     | memberSet a bs = subSet as bs 
     | otherwise = False 

Answer 1

a olduğunda Set aEq örneğidir olmasıdır. Aslında a'un, Eq'un bir örneği tamamen başka bir konudur; Bu sadece memberSet ile == ile iki Set s karşılaştırmanıza izin verirken, sadece elemanları karşılaştırıyorsunuz.

Integer -> Integer türünü düşünün. Bu, açık olması gereken nedenlerden dolayı Eq'un bir örneği değildir. Set bu türde öğeler içeriyorsa, memberSet'un nasıl çalışmasını beklersiniz?

Burada gerçekleştirmeyi umuyor olmanızın, Eq numaralı bir eleman türüyle yalnızca Set s sağlanmasını sağlamasıdır. Eğer öyleyse, bu çok farklı bir sorun, ama aynı zamanda çoğunlukla gereksizdir - Set s işlevlerini kullanarak Eq kısıtlamayı kullanarak aynı amaç sonunda hizmet vermektedir.

Neden the standard Data.Set module'a bir göz atmıyorsunuz? Setlerde çalışan işlevlerinin çoğunun, kullanılan iç temsilin bir ikili arama ağacı olduğu gerçeğini yansıtan bir Ord kısıtlamasına sahip olduğunu unutmayın.

Answer 2

kısıtlamalar bir GADT kullanarak fonksiyonları üzerine gerekli değildir, böylece bunun eğlenceli, bunu sağlayabilir Sadece için: Çeşidi Insert yapıcı Eq kısıtlamayı koyarak

{-# LANGUAGE GADTs #-} 
module Set where 

data Set x where 
    EmptySet :: Set a 
    Insert :: Eq a => a -> Set a -> Set a 

instance Show a => Show (Set a) where 
    show EmptySet = "{}" 
    show xs = "{" ++ show' xs ++ "}" 
     where 
     show' (Insert a EmptySet) = show a 
     show' (Insert a ys) = show a ++ ", " ++ show' ys 

instance Eq (Set a) where 
    (Insert x xs) == (Insert y ys) = x == y && xs == ys 
    EmptySet == EmptySet = True 
    _ == _ = False 

memberSet :: a -> Set a -> Bool 
memberSet x (Insert y ys) = x == y || memberSet x ys 
memberSet _ _ = False 

subSet :: Set a -> Set a -> Bool 
subSet EmptySet _ = True 
subSet (Insert a as) bs 
    | memberSet a bs = subSet as bs 
    | otherwise = False 

biz

1. yok boş olmayan seti değil Eq yılında türleri için inşa edilebilir sağlayabilirsiniz.
2. Insert yapıcısına model eşleştiğinde, Eq bağlamı (ve sözlüğü) kullanılabilir; bu nedenle, işlev türü imzasında belirtmemize gerek yoktur.