I am using Glasgow Haskell Compiler, Version 7.8.3, stage 2 booted by GHC version 7.6.3.
I attempted to use the following data definition for a List type in Haskell:
data Eq a => List a = Nil | Cons a (List a)
However, the -XDatatypeContexts flag is required, depricated, and even removed from the language by default. It is widely viewed as a misfeature of the language. I also do not want to have to use special flags for my definition of List since I am trying to replicate the functionality of the existing list type.
Then I was able to use the following segment of code instead:
data List a where
Nil :: List a
Cons :: Eq a => a -> List a -> List a
It runs fine. The visible issue with this solution is that now I need to use the -XGADTs flag, which I still don't want to depend on in this case since it is not necessary for the built in version of list to function. Is there a way to restrict the type within Cons to be Eq a so that I can compare two lists without the need for compiler flags and without using the derived keyword?
The remaining code is as follows:
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")
I see that the following solution works:
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")
However, for some reason, it does not work with a manual definition for Eq (Equals here).
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")
I get the following error:
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")
However, by using GADT's, I can show that my Equal class does actually function. This code works:
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")
However, I have to use instance Equal (List a) where instead of instance Equal a => Equal (List a) where otherwise I get the error:
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")
It looks like you're trying to restrict lists to only be able to hold values that implement Eq, and you can't do that without extensions. You can, however, tell the compiler how to compare two List as when a has a type that implements Eq. There are two easy ways to do this. The simplest is with a deriving statement:
data List a = Nil | Cons a (List a) deriving (Eq)
Or you can define it manually:
instance Eq a => Eq (List a) where
(Cons a b) == (Const c d) = (a == c) && (b == d)
Nil == Nil = True
_ == _ = False
Now whenever you fill your List type with something that implements Eq, the list will also be comparable using ==. There's no need to restrict the values that can be inside Cons. You can certainly have a normal list of functions, like
fs1 :: [Int -> Int]
fs1 = [(+1), (*3), (+2), (*4)]
Or in your case
fs2 :: List (Int -> Int)
fs2 = Cons (+1) $ Cons (*3) $ Cons (+2) $ Cons (*4) Nil
Which can be used as
> map ($ 10) fs1
[11, 30, 12, 40]
And given
map' :: (a -> b) -> List a -> List b
map' f Nil = Nil
map' f (Cons x xs) = Cons (f x) (map' f xs)
Then
> map' ($ 10) fs2
Cons 11 (Cons 30 (Cons 12 (Cons 40 Nil)))
Although to actually view it in GHCi you should also derive Show:
data List a = Nil | Cons a (List a) deriving (Eq, Show)
There are several other useful typeclasses that can be derived in GHC, too.
To make it work with your custom Equal typeclass, you'll have to write multiple instances by hand:
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
Now because you have an instance Equal Int and Equal a => Equal (List a), you can compare two 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
For whatever type you want to store in a List and use =+= on, you'll have to implement Equal for that type.