BEGIN 16_10_14_ClassInstances.lhs

EXAMPLES OF USER-DEFINED INSTANCES OF PRE-DEFINED CLASSES

We give 4 examples of types or datatypes:
 
   "Bool -> Bool"     (in Example 1)
   "Bool -> Int"      (in Example 2)
   "Int -> Bool"      (in Example 3)
   "Int -> Int"       (in Example 4)

We show that it is possible to make the first and second types
instances of "==" and "<", and then show that we canNOT make
the third and fourth types instances of "==" and "<".

BEGIN EXAMPLE 1: Defining Equality and Ordering on the 
                 Function Type "Bool -> Bool"

The type "Bool -> Bool" is not by default in the class Eq, i.e.
the Haskell interpreter (or compiler) refuses to let "==" on
"Bool -> Bool" be inherited -- using the "deriving" feature -- 
from the built-in standard notion of "==" on Bool. That is, 
if we try something like:

   type BoolBoolFn = Bool -> Bool                               -- (1)
                 deriving (Eq)                                  -- (2)

we will again get an error message, saying that we cannot use the 
"deriving" clause with a type-declaration. So, we may be tempted
to try a newtype-declaration instead:              

   newtype BoolBoolFn = BBF (Bool -> Bool)                      -- (3)
                    deriving (Eq)                               -- (4)
              
But again we get an error message, a different one this time, saying 
that "==" on BoolBoolFn should be defined explicitly by the user. So, we
now try instead:

>  newtype BoolBoolFn = BBF (Bool -> Bool)                      -- (3)
 
>  instance Eq BoolBoolFn where                                 -- (5)
>    (==) (BBF f) (BBF g) =                                     -- (6)
>        (f True == g True) && (f False == g False)             -- (7)

This time we get no error code. To make BoolBoolFn an instance of the 
class Ord, we also have to do it explicitly, i.e. without using the
"deriving" clause:

>  instance Ord BoolBoolFn where                                -- (8)
>    (<=) (BBF f) (BBF g) =                                     -- (9)
>        (f True <= g True) && (f False <= g False)             -- (10)

The predefined type "Bool -> Bool" and the user-defined BoolBoolFn are
isomorphic, i.e. copies of each other, except that every member of the
user-defined is wrapped with the constructor "BBF". Expressing this
correspondence between "Bool -> Bool" and BoolBoolFn, we can write:

>  wrapBoolBoolFn :: (Bool -> Bool) -> BoolBoolFn               -- (11)
>  wrapBoolBoolFn f = (BBF f)                                   -- (12)

>  unwrapBoolBoolFn :: BoolBoolFn -> (Bool -> Bool)             -- (13)
>  unwrapBoolBoolFn (BBF f) = f                                 -- (14)

To experiment with the preceding declarations, we define all
the functions of type "Bool -> Bool" -- there are exactly 4
of them:

>  f1, f2, f3, f4 :: Bool -> Bool                               -- (15)
>  f1 _ = True                                                  -- (16)
>  f2 _ = False                                                 -- (17)
>  f3 x = x                                                     -- (18)
>  f4 x = not x                                                 -- (19)

And we define all the functions of type BoolBoolFn:

>  f1', f2', f3', f4' :: BoolBoolFn                             -- (20)
>  f1' = wrapBoolBoolFn f1                                      -- (21)
>  f2' = wrapBoolBoolFn f2                                      -- (22)
>  f3' = wrapBoolBoolFn f3                                      -- (23)
>  f4' = wrapBoolBoolFn f4                                      -- (24)

END EXAMPLE 1

BEGIN EXAMPLE 2: Defining Equality and Ordering on the 
                 Function Type "Bool -> Int"

We omit most of the details, just pointing out the differences with
Example 1. The counterpart of (3) here is:

>  newtype BoolIntFn = BIF (Bool -> Int)                        -- (25)

The counterparts of (5), (6) and (7) are:

>  instance Eq BoolIntFn where                                  -- (26)
>    (==) (BIF f) (BIF g) =                                     -- (27)
>        (f True == g True) && (f False == g False)             -- (28)

The counterparts of (8), (9) and (10) are:

>  instance Ord BoolIntFn where                                 -- (29)
>    (<=) (BIF f) (BIF g) =                                     -- (30)
>        (f True <= g True) && (f False <= g False)             -- (31)

The counterparts of (11), (12), (13) and (14) are:

>  wrapBoolIntFn :: (Bool -> Int) -> BoolIntFn                  -- (32)
>  wrapBoolIntFn f = (BIF f)                                    -- (33)

>  unwrapBoolIntFn :: BoolIntFn -> (Bool -> Int)                -- (34)
>  unwrapBoolIntFn (BIF f) = f                                  -- (35)

We cannot define all the functions of type Bool -> Int or, equivalently,
of type BoolIntFn -- because there are infinitely many of them. But we
can define a few of them:

>  g1, g2, g3, g4, g5, g6 :: Bool -> Int                        -- (36)
>  g1 _ = 5                                                     -- (37)
>  g2 _ = 10                                                    -- (38)
>  g3 _ = 15                                                    -- (39)
>  g4 True  = 10                                                -- (40)
>  g4 False = 15                                                -- (41)
>  g5 True  = 15                                                -- (42)
>  g5 False = 10                                                -- (43)
>  g6 True  = 5                                                 -- (44)
>  g6 False = 15                                                -- (45)

>  g1', g2', g3', g4', g5', g6' :: BoolIntFn                    -- (46)
>  g1' = wrapBoolIntFn g1                                       -- (47)
>  g2' = wrapBoolIntFn g2                                       -- (48)
>  g3' = wrapBoolIntFn g3                                       -- (49)
>  g4' = wrapBoolIntFn g4                                       -- (50)
>  g5' = wrapBoolIntFn g5                                       -- (51)
>  g6' = wrapBoolIntFn g6                                       -- (52)

END EXAMPLE 2

BEGIN EXAMPLE 3: How Can We Define Equality and Ordering on the 
                 Function Type "Int -> Bool"?

We can try, as in Example 1 and Example 2, but we will fail. Writing
the counterpart of (3) is not a problem:

>  newtype IntBoolFn = IBF (Int -> Bool)                       -- (53)

But we will encounter a problem when we try to write the counterparts 
of (5), (6) and (7) -- because we have to test the equality of infinitely 
many cases.

Is the type IntBoolFn useless? No, there are good uses for it; all we
have here is that we cannot make it an instance of Eq -- and therefore
of Ord also.

END EXAMPLE 3

BEGIN EXAMPLE 4: How Can We Define Equality and Ordering on the 
                 Function Type "Int -> Int"?

We can try as in Example 1 and Example 2, but we will fail. Writing
the counterpart of (3) is not a problem, just as in Example 3:

>  newtype IntIntFn = IIF (Int -> Int)                       -- (54)

But, here as in Example 3, we will fail when we try to write the 
counterparts of (5), (6) and (7) -- because we have to test the 
equality of infinitely many cases.

END EXAMPLE 4

BEGIN EXAMPLE 5: Continuation of Example 3.

We cannot make IntBoolFn an instance of Eq and Ord, as shown in
Example 3 above. But if we consider a "finite aproximation" of 
IntBoolFn, then we will not run into the same obstacle, as shown
next.

>  newtype IntBoolFn' = IBF' (Int -> Bool)

We choose to make two functions, f and g, of type "Int -> Bool" equal
if f(x) == g(x) for every x in the FINITE interval [0..1000]:

>  instance Eq IntBoolFn' where                                  
>    (==) (IBF' f) (IBF' g) =
>        foldr (&&) 
>              True 
>              (zipWith (==) [ f(x) | x <- interval ] [ g(y) | y <- interval])
>              where interval = [0..1000]

Given two functions, f and g, of type "Int -> Bool", we choose to 
make "f <= g" just in case f(x) <= g (x) for every x in the FINITE
interval [0..1000]:

>  instance Ord IntBoolFn' where
>    (<=) (IBF' f) (IBF' g) =
>        foldr (&&)
>              True
>              (zipWith (<=) [ f(x) | x <- interval ] [ g(y) | y <- interval ])
>              where interval = [0..1000]

>  wrapIntBoolFn' :: (Int -> Bool) -> IntBoolFn'                  
>  wrapIntBoolFn' f = (IBF' f)                                    

>  unwrapIntBoolFn' :: IntBoolFn' -> (Int -> Bool)                
>  unwrapIntBoolFn' (IBF' f) = f                                  

To experiment with the preceding declarations, we define a few
functions of type "Int -> Bool": 

>  h1, h2, h3, h4, h5, h6, h7, h8, h9, h10 :: Int -> Bool
>  h1 = even
>  h2 = odd
>  h3 x = (x `mod` 3 == 0)
>  h4 x = (h1 x) && (h3 x)
>  h5 x = (h2 x) && not (h3 x)
>  h6 x 
>      | x <= 1000      = h1 x
>      | otherwise      = h2 x
>  h7 x
>      | x <= 2000      = h2 x
>      | otherwise      = h1 x
>  h8 x 
>      | x <= 3000      = h3 x
>      | otherwise      = False
>  h9 _ = True
>  h10 _ = False

And we define the corresponding functions of type IntBoolFn':

>  h1', h2', h3', h4', h5', h6', h7', h8' :: IntBoolFn'
>  h1' = wrapIntBoolFn' h1
>  h2' = wrapIntBoolFn' h2
>  h3' = wrapIntBoolFn' h3
>  h4' = wrapIntBoolFn' h4
>  h5' = wrapIntBoolFn' h5
>  h6' = wrapIntBoolFn' h6
>  h7' = wrapIntBoolFn' h7
>  h8' = wrapIntBoolFn' h8
>  h9' = wrapIntBoolFn' h9
>  h10' = wrapIntBoolFn' h10

END EXAMPLE 5

BEGIN EXERCISE:

This continues Example 4 above. Consider the datatype

>  newtype IntIntFn' = IIF' (Int -> Int)      

Using Example 5 as a guide, show that we can make IntIntFn' 
and instance of Eq and Ord, when we restrict (==) and (<=)
to a finite interval of the integers.

END EXERCISE 

END 16_10_14_ClassInstances.lhs