# 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