{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
data LinkedList a = Cons a (LinkedList a) | End deriving Show
data PairList a = Pair a a (PairList a) | PairEnd deriving Show

class List a where
  len :: a -> Integer

instance List (LinkedList a) where
  len End = 0
  len (Cons _ xs) = 1 + len xs

instance List (PairList a) where
  len PairEnd = 0
  len (Pair _ _ xs) = 2 + len xs

class List a => Reverse a where
  rev :: a -> a

instance {-# OVERLAPPABLE #-} List a => Reverse a where
  rev = id

instance Reverse (PairList a) where
  rev (Pair x y ys) = Pair y x (rev ys)
  rev PairEnd = PairEnd

main = do
  let linkedList = Cons 1 (Cons 2 End)
  print linkedList
  print $ rev linkedList
  let pairList = Pair 1 2 (Pair 3 4 PairEnd)
  print pairList
  print $ rev pairList