如何在没有GADT或数据类型上下文的情况下定义List的Eq实例

Question

我在用Glasgow Haskell Compiler, Version 7.8.3, stage 2 booted by GHC version 7.6.3.

我试图在Haskell中对List类型使用以下数据定义:

data Eq a => List a = Nil | Cons a (List a)

但是,-XDatatypeContexts默认情况下,该标志是必需的,已删除的,甚至是从语言中删除的.它被广泛视为语言的错误.我也不想为List的定义使用特殊标志,因为我试图复制现有列表类型的功能.然后我能够使用以下代码段:

data List a where
 Nil :: List a
 Cons :: Eq a => a -> List a -> List a

它运行正常.这个解决方案的明显问题是现在我需要使用-XGADTs标志,在这种情况下我仍然不想依赖它,因为内置版本的列表不需要运行.有没有办法限制其中的类型Cons,Eq a以便我可以比较两个列表,而无需编译器标志和不使用derived关键字？其余代码如下:

instance Eq (List a) where
 (Cons a b) == (Cons c d) = (a == c) && (b == d)
 Nil == Nil = True
 _ == _ = False
testfunction = Nil :: List Int
main = print (if testfunction == Nil then "printed" else "not printed")

我看到以下解决方案有效:

data List a = Nil | Cons a (List a)
instance Eq a => Eq (List a) where
 (Cons a b) == (Cons c d) = (a == c) && (b == d)
 Nil == Nil = True
 _ == _ = False
testfunction = Nil :: List Int
main = print (if testfunction == Nil then "printed" else "not printed")

但是,出于某种原因,它不适用于Eq的手动定义(此处为等于).

class Equal a where  
 (=+=) :: a -> a -> Bool  
 (/+=) :: a -> a -> Bool  
 x =+= y = not (x /+= y)  
 x /+= y = not (x =+= y)
data List a = Nil | Cons a (List a)
instance Equal a => Equal (List a) where
 (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
 Nil =+= Nil = True
 _ =+= _ = False
testfunction = Nil :: List Int
main = print (if testfunction =+= Nil then "printed" else "not printed")

我收到以下错误:

No instance for (Equal Int) arising from a use of ‘=+=’
    In the expression: testfunction =+= Nil
    In the first argument of ‘print’, namely
      ‘(if testfunction =+= Nil then "printed" else "not printed")’
    In the expression:
      print (if testfunction =+= Nil then "printed" else "not printed")

但是,通过使用GADT,我可以证明我的Equal类确实起作用.此代码有效:

class Equal a where  
 (=+=) :: a -> a -> Bool  
 (/+=) :: a -> a -> Bool  
 x =+= y = not (x /+= y)  
 x /+= y = not (x =+= y)
data List a where
 Nil :: List a
 Cons :: Equal a => a -> List a -> List a
instance Equal (List a) where
 (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
 Nil =+= Nil = True
 _ =+= _ = False
testfunction = Nil :: List Int
main = print (if testfunction =+= Nil then "printed" else "not printed")

但是,我必须使用instance Equal (List a) where而不是instance Equal a => Equal (List a) where否则我得到错误:

No instance for (Equal Int) arising from a use of ‘=+=’
    In the expression: testfunction =+= Nil
    In the first argument of ‘print’, namely
      ‘(if testfunction =+= Nil then "printed" else "not printed")’
    In the expression:
      print (if testfunction =+= Nil then "printed" else "not printed")

Answer 1

看起来您试图将列表限制为只能保存实现的值,Eq如果没有扩展名,则无法执行此操作.但是,您可以告诉编译器List a在a具有实现类型的情况下如何比较两个s Eq.有两种简单的方法可以做到这一点.最简单的是使用派生语句:

data List a = Nil | Cons a (List a) deriving (Eq)

或者您可以手动定义它:

instance Eq a => Eq (List a) where
    (Cons a b) == (Const c d) = (a == c) && (b == d)
    Nil == Nil = True
    _ == _ = False

现在,无论何时List使用实现的东西填充您的类型Eq,列表也将具有可比性==.没有必要限制可以在里面的值Cons.你当然可以有一个正常的功能列表,比如

fs1 :: [Int -> Int]
fs1 = [(+1), (*3), (+2), (*4)]

或者在你的情况下

fs2 :: List (Int -> Int)
fs2 = Cons (+1) $ Cons (*3) $ Cons (+2) $ Cons (*4) Nil

哪个可以用作

> map ($ 10) fs1
[11, 30, 12, 40]

并给出

map' :: (a -> b) -> List a -> List b
map' f Nil = Nil
map' f (Cons x xs) = Cons (f x) (map' f xs)

然后

> map' ($ 10) fs2
Cons 11 (Cons 30 (Cons 12 (Cons 40 Nil)))

虽然要在GHCi中实际查看它,您还应该派生Show:

data List a = Nil | Cons a (List a) deriving (Eq, Show)

还有一些其他有用的类型类也可以在GHC中派生出来.

要使它适用于您的自定义Equal类型类,您必须手动编写多个实例:

class Equal a where
    (=+=) :: a -> a -> Bool
    (/+=) :: a -> a -> Bool
    x =+= y = not (x /+= y)
    x /+= y = not (x =+= y)

instance Equal Int where
    x =+= y = x == y

instance Equal a => Equal (List a) where
    (Cons a b) =+= (Cons c d) = (a =+= c) && (b =+= d)
    Nil =+= Nil = True
    _ =+= _ = False

现在,因为你有一个实例Equal Int和Equal a => Equal (List a),你可以比较两个List IntS:

> let x = Cons 1 (Cons 2 (Cons 3 Nil)) :: List Int
> let y = Cons 1 (Cons 2 (Cons 3 Nil)) :: List Int
> x =+= y
True
> x =+= Nil
False

对于您想要存储List和使用的任何类型=+=,您必须Equal为该类型实现.