import Prelude hiding (elem)

--elem :: Int -> [Int] -> Bool
--elem :: Char -> [Char] -> Bool
elem :: Eq a => a -> [a] -> Bool
elem x []     = False
elem x (y:ys) = x == y || elem x ys

{-
-- The type class Eq:
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

-}

-- Note: polymorphism is different from overloading

data BW = Black | White
 deriving (Read, Show)

instance Eq BW where
  --(==) :: BW -> BW -> Bool
  Black == Black = True
  Black == White = False
  White == Black = False
  White == White = True

  --(/=) :: BW -> BW -> Bool
  x /= y = not (x == y)

data IntTree = Empty | Node IntTree Int IntTree
  deriving Show

t123 :: IntTree
t123 = Node (Node Empty 1 Empty) 2 (Node Empty 2 Empty)

instance Eq IntTree where
  Empty         == Empty         = True
  Node l1 i1 r1 == Node l2 i2 r2 = l1 == l2 && i1 == i2 && r1 == r2
  Empty         == Node _ _ _    = False
  Node _ _ _    == Empty         = False

  t1 /= t2 = not (t1 == t2)


data Tree a = EmptyP | NodeP (Tree a) a (Tree a)
  deriving (Read, Show, Ord)

tA :: Tree Char
tA = NodeP EmptyP 'A' EmptyP

-- Instance w.r.t. Eq-constrained element types:
instance Eq a => Eq (Tree a) where
  EmptyP         == EmptyP         = True
  NodeP l1 i1 r1 == NodeP l2 i2 r2 = l1 == l2 && i1 == i2 && r1 == r2
  EmptyP         == NodeP _ _ _    = False
  NodeP _ _ _    == EmptyP         = False

  -- t1 /= t2 = not (t1 == t2)


{-
-- The type class Eq with predefined functions:
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

  x == y = not (x /= y)
  x /= y = not (x == y)
-}


---------------------------------------------------------------------------
-- More predefined type classes:

-- Compare values:
{-
data Ordering = LT | EQ | GT

class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<=), (<), (>=), (>) :: a -> a -> Bool
  max, min :: a -> a -> a
  -- predefined definitions...
-}
-- Minimal instance definition must contain 'compare' or '<='

{-
instance Ord a => Ord (Tree a) where
  EmptyP         <= EmptyP        = True
  EmptyP         <= NodeP _ _ _   = True
  NodeP _ _ _    <= EmptyP        = False
  NodeP l1 i1 r1 <= NodeP l2 i2 r2 = l1 < l2
                                  || (l1 == l2 && i1 < i2)
                                  || (l1 == l2 && i1 == i2 && r1 <= r2)
-}

{-

-- All sorts of numbers:
class Num a where
  (+) :: a -> a -> a
  (*) :: a -> a -> a
  ...

instance Num Int ...
instance Num Float ...


-- Showable types:
class Show a where
  show :: a -> String

-- Readable types:

type ReadS a = String -> [(a,String)]

class Read a where
  reads :: ReadS a

read :: Read a => String -> a
read s = case reads s of [(x,"")] -> x
                         _        -> error "no parse"
-}