Section 12: Polymorphism

Polymorphism

Polymorphism, means “ploy” and “morphi”, which is “many shapes”. It is also known as “type scheme”. A value is polymorphic if there is more than one type it can have.

  • Parameteric Polymorphism: parametric polymorphism refers to when the type of a value contains one or more (unconstrained) type variables, so that the value may adopt any type that results from substituting those variables with concrete types.

    length :: [a] -> Int
    fst :: (a, b) -> a
    snd :: (a, b) -> b
    
    length :: forall a. [a] -> Int
    fst :: forall a b. (a, b) -> a
    

    Note

    In Haskell, type variables always begin in lowercase whereas concrete types like Int or String always start with an uppercase letter.

    Note

    Also note, in languages like Haskell, functions are values of some function types.

  • Ad-hoc Polymorphism: ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types.

    -- type 'a' belongs to class 'Eq' if there is a function named
    -- '(==)', of the appropriate types, defined on it
    class Eq a where
            (==) :: a -> a -> Bool
    
    instance Eq Integer where
            x == y = x `integerEq` y
    
    instance Eq Float where
            x == y = x `floatEq` y
    
    memberOf :: (Eq a) => a -> [a] -> Bool
    

    Note

    the equality operator, == is a function. So are +, *, -, / and pretty much all operators. If a function is comprised only of special characters, it’s considered an infix function by default. If we want to examine its type, pass it to another function or call it as a prefix function, we have to surround it in parentheses.

    Note

    The function member has the type a -> [a] -> Bool with the context (Eq a), which constrains the types which a can range over to those a which belong to the Eq class. (Note: Haskell => can be called a ‘class constraint’.)

Practice

  1. Write a polymorphic list
  2. Write a list_len function for it
  3. Write a list_get function for it
  4. Write a identity function for it
data List a = Nil
        | Cons a (List a)

list_len :: (List a) -> Int
list_len (Nil) = 0
list_len (Cons _ xs) = 1 + list_len (xs)

list_eq :: (Eq a) => List a -> List a -> Bool
list_eq Nil Nil = True
list_eq Nil _ = False
list_eq _ Nil = False
list_eq (Cons x xs) (Cons y ys) = (x == y) && (list_eq xs ys)

instance (Eq a) => Eq (List a) where
        x == y = x `list_eq` y

list_get :: List a -> Int -> a
list_get (Cons x _) 0 = x
list_get (Cons _ xs) index = list_get xs (index - 1)

Example

polyset.hs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
module PolySet where

class IsSet s where
  empty :: s a
  insert :: Ord a => s a -> a -> s a
  contains :: (Ord a, Eq a) => a -> s a -> Bool
  
  inserts :: Ord a => s a -> [a] -> s a
  inserts s (x:xs) = inserts (insert s x) xs
  inserts s []     = s

data SetList a =
    Empty
  | Set [a]
  deriving Show   

instance IsSet SetList where
  empty = Empty

  insert (Set l) x = Set (x:l)
  insert (Empty) x = Set [x]

  contains x (Empty) = False
  contains x (Set l) = x `elem` l

data SetTree a =
    Leaf
  | Node a (SetTree a) (SetTree a)
  deriving Show   

instance IsSet SetTree where
  empty = Leaf

  insert (Leaf       ) x = Node x Leaf Leaf
  insert (Node y s s') x =
    if x < y then 
      Node y (insert s x) s' 
    else
      Node y s (insert s' x)

  contains x (Leaf       ) = False
  contains x (Node y s s') =
    if y == x then
      True
    else if x < y then
      contains x s
    else
      contains x s'

get :: (IsSet s) => s a
get = empty

both :: (Ord a, IsSet s1, IsSet s2) => s1 a -> s2 a -> a -> Bool
both s1 s2 e = (contains e s1) && (contains e s2)


main :: IO ()
main = do 
       let s1 = empty :: SetList int
           s2 = insert s1 1
           s3 = insert s2 2
           b1 = contains 2 s3
           b2 = contains 3 s3
       putStrLn (show b1)
       putStrLn (show b2)

       let
           s21 = empty :: SetTree int
           s22 = insert s21 1
           s23 = insert s22 3
           b21 = contains 3 s23
           b22 = contains 4 s23

       putStrLn (show b21)
       putStrLn (show b22)

       let
          b1 = both s3 s23 1
          b2 = both s3 s23 2
       putStrLn (show b1)
       putStrLn (show b2)

polyset.py

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
def both1(s1, s2, e):
    if (contains(s1, e) and contains(s2, e)):
        return True
    else:
        return False

def both2(s1, s2, e):
    if (s1.contains(e) and s2.contains(e)):
        return True
    else:
        return False

# ******************************************* #

def both(s1, s2, e):
    if (s1.get_type().contains(s1, e) and s2.get_type().contains(s2, e)):
        return True
    else:
        return False

class SetList(object):
    @staticmethod
    def empty():
        return SetList()

    @staticmethod
    def insert(s, e):
        if (s.m_lst == None):
            return SetList([e])
        else:
            return SetList([e] + s.m_lst)

    @staticmethod
    def contains(s, e):
        return e in s.m_lst

    def __init__(self, lst=None):
        self.m_lst = lst

    def get_type(self):
        return SetList

s1 = SetList.empty()
s2 = SetList.insert(s1, 1)
s3 = SetList.insert(s2, 2)

b = SetList.contains(s3, 2)
print b
b = SetList.contains(s3, 3)
print b

class SetTree(object):
    @staticmethod
    def empty():
        return SetTree()

    @staticmethod
    def insert(s, e):
        if (s.m_node == None):
            return SetTree((e, SetTree(), SetTree()))
        else:
            node = s.m_node
            if e < node[0]:
                sl = SetTree.insert(node[1], e)
                return SetTree((node[0], sl, node[2]))
            else:
                sr = SetTree.insert(node[2], e)
                return SetTree((node[0], node[1], sr))

    @staticmethod
    def contains(s, e):
        node = s.m_node
        if (node == None):
            return False
        elif e == node[0]:
            return True
        elif e < node[0]:
            return SetTree.contains(node[1], e)
        else:
            return SetTree.contains(node[2], e)

    def __init__(self, node=None):
        self.m_node = node

    def get_type(self):
        return SetTree

s21 = SetTree.empty()
s22 = SetTree.insert(s21, 1)
s23 = SetTree.insert(s22, 3)

b = SetTree.contains(s23, 3)
print b
b = SetTree.contains(s23, 4)
print b

b = both(s3, s23, 1)
print b
b = both(s3, s23, 2)
print b

Solution: polyset.hs polyset.py Makefile