Как определить Eq-экземпляр списка без GADT или контекстов типа данных

Похоже, вы пытаетесь ограничить списки, чтобы они могли содержать только значения, реализующие Eq, и вы не можете сделать это без расширений. Однако вы можете указать компилятору, как сравнивать два List a, когда a имеет тип, реализующий 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 Int:

> 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 для этого типа.

Обычным решением для этого является использование этой структуры:

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

Заметил, что я добавил Eq a в качестве ограничения к экземпляру, а не к типу данных. Таким образом, все списки, которые вы могли бы сравнить на равенство так, как вы пытаетесь его написать, можно сравнить на равенство, но вы также допускаете существование списков вещей, которые нельзя сравнивать на равенство. И это поддерживается каждой версией Haskell, с которой вы столкнетесь, даже очень старой, без расширений.

Затем этот подход также хорошо расширяется, когда вы хотите добавить экземпляр Show, экземпляр Ord и т. д.; чтобы сделать это по-своему, вы должны продолжать возвращаться и делать структуру данных более ограничительной, добавляя больше ограничений (потенциально ломая существующий код, который работал нормально, потому что ему не нужны были эти экземпляры). В то время как если вы оставите тип данных без ограничений и просто сделаете свои экземпляры Show a => Show (List a), Ord a => Ord (List a) и т. д., тогда вы сможете показывать и списки порядков типов, которые поддерживают оба типа, но вы все равно можете иметь (и показывать) списки типов, которые поддерживают Show, но не Ord, и наоборот.

Кроме того, существует множество полезных классов типов для параметризованных типов (таких как List a), которые требуют, чтобы они были полностью универсальными в своем параметре типа. Примеры: Functor, Applicative, Monad; невозможно правильно реализовать их для типа списка с ограничениями, который вы пытаетесь создать.

Хотя можно создавать ограниченные списки, как вы пытаетесь (но только с помощью расширений, как вы обнаружили), обычно гораздо полезнее оставить ваши типы данных полностью универсальны в своем параметре типа, и если конкретное использование вашего типа должно налагать ограничения на параметр типа, вы накладываете их на этом сайте использования, а не на каждом использовании тип данных. Это должно быть вашей «настройкой по умолчанию»; откажитесь от него, когда у вас есть веская причина (у вас вполне может быть такая причина здесь, но вы не указали ее нам в вопросе, поэтому никто не может порекомендовать лучший способ справиться с этим).