{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances,FunctionalDependencies #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE OverlappingInstances #-}

-- Comparing types by shape: by the top-level type constructor and arity

module ConEQ where

data HTrue
data HFalse

instance Show HTrue where
    show _ = "HT"

instance Show HFalse where
    show _ = "HF"

-- The most general type equality
class  TypeEq x y b | x y -> b
instance TypeEq x x HTrue
instance b ~ HFalse => TypeEq x y b


-- To compare types by shape, we `normalize' them before applying
-- TypeEq. We replace all arguments of the type constructor with ().

-- Yet another use of overlapping instances
class Normalize t r | t -> r

instance (c ())   ~ r => Normalize (c x) r
instance (c () ()) ~ r => Normalize (c x y) r
instance (c () () ()) ~ r => Normalize (c x y z) r
-- add instances for type constructors of higher arities
-- Alas, we cannot write Normalize generically for all arities
-- because type class arguments have fixed kinds.

-- The default instance
instance y ~ x => Normalize x y

-- Examples

teq :: TypeEq x y b => x -> y -> b
teq = undefined

top_eq :: (Normalize a a', Normalize b b', TypeEq a' b' r) =>
          a -> b -> r
top_eq = undefined

test1 = teq (undefined::Int) (undefined::Char)
-- HF

test1' = top_eq (undefined::Int) (undefined::Char)
-- HF

test2 = teq (undefined::[Int]) (undefined::[Int])
-- HT

test2' = top_eq (undefined::[Int]) (undefined::[Int])
-- HT

test3 = teq (undefined::Maybe Bool) (undefined::Maybe Char)
-- HF

test3' = top_eq (undefined::Maybe Bool) (undefined::Maybe Char)
-- HT

test4 = top_eq (undefined::Maybe Bool) (undefined::[Char])
-- HF

test5 = top_eq (undefined::Either Int Char) (undefined::Either Char Int)
-- HT

test6 = top_eq (undefined::Either Int Char) (undefined::[Char])
-- HF