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
orString
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 typea -> [a] -> Bool
with the context(Eq a)
, which constrains the types whicha
can range over to thosea
which belong to theEq
class. (Note: Haskell=>
can be called a ‘class constraint’.)
Practice¶
- Write a polymorphic list
- Write a
list_len
function for it - Write a
list_get
function for it - 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