Programming Fundamentals

Programming Fundamentals Lesson 11 Polymorphic functions

Today, we will… • Study polymorphic functions. • Polymorphic functions accept arguments and have result in any of a class of types, not necessarily in types fully specified in the signature. • Actually, many functions from the Prelude are polymorphic. 31-Dec-10

Programming Fundamentals - 11 © Pedro Guerreiro

2

Polymorphism wanted! • As we have seen with quicksort, some algorithms apply to various types. • Even so, for every new type, we have to program new functions, since those prepared for arguments of type Int cannot be used for arguments of type String, for example. • On the other hand, we know that some Prelude functions can be used with arguments of various types:

31-Dec-10

This is a list of integers. Hugs> length [3,5,7,9] 4 Hugs> length [True, False] This is a list of Booleans. 2 Hugs> sum [1..5] This is a list of integers. 15 Hugs> sum [1, 0.5, 0.25, 0.125, 0.0625] 1.9375 Programming Fundamentals - 11 © Pedro Guerreiro 3 This is a list of doubles.

Length • In the Prelude, function length is polymorphic. • Our own lengthList function is not. It works only lengthList :: [Int] -> Int with lists of Int. lengthList [] = 0

Main> lengthList [2..99] lengthList (_:xs) = 1 + lengthList xs 98 Main> lengthList [[1,2],[],[9,8,7,6]] ERROR - Type error in application *** Expression : lengthList [[1,2],[],[9,8,7,6]] *** Term : [[1,2],[],[9,8,7,6]] *** Type : [[a]] *** Does not match : [Int] Main> length [2..99] 98 Main> length [[1,2],[],[9,8,7,6]] 31-Dec-103 Programming Fundamentals - 11 © Pedro Guerreiro

4

Polymorphic length • Indeed, if we were to program a new function for the length of lists of Strings, the equations would be the same; only the signature differs. • Well, let us use a signature that matches lists of any type:

lengthList :: [a] -> Int lengthList [] = 0 lengthList (_:xs) = 1 + lengthList xs

31-Dec-10

Main> lengthList [[1,2],[],[9,8,7,6]] 3 Main> lengthList [True, False] 2 Main> lengthList [1, 1.1, 1.11, 1.111] 4 Main> lengthList [100, Programming Fundamentals - 11 95..1] © Pedro Guerreiro 20

5

Polymorphic sum • Let’s use the same technique to program the sum of lists of any type: sumList :: [a] -> a sumList [] = 0 sumList (x:xs) = x + sumList xs

By analysing the equations, Hugs inferred that the type of this function Main> :r ERROR file:polymorphism.hs:11 - Inferred type should be [Integer] -> is not general enough [Integer]. However, *** Expression : sumList we stated that it was *** Expected type : [a] -> a more general than *** Inferred type : [Integer] -> Integer that: [a]->a. 31-Dec-10


6

Polymorphic sum, constrained • The problem with the previous definition is that not all types have addition, via an operator (+). • In this case, we must specify, in the signature, that the polymorphic type must be an instance of a numeric type: sumList :: Num a => [a] -> a Num is a class type, representing numeric sumList [] = 0 types. This constraint sumList (x:xs) = x + sumList xs means that type a can Main> sumList [1,2,4,8,16] 31 Main> sumList [1, 1/2, 1/4, 1/8, 1/16] 1.9375 31-Dec-10

be any type, so long as it is a numeric type .


7

Type classes • Num, for numeric types with (+), (-), (*). • Eq, for types with equality, (==), (/=). • Ord, for types with order, (=) and also (==) and (/=) which means the Ord is a subclass of Eq. • Integral, for the numeric types that also have div and mod. • Fractional, for numeric types that have (/). 31-Dec-10


8

Equality • Function elemList requires equality. The first argument must be of a type of class Eq, and the second argument must be a list of the same type. elemList :: Eq a => a -> [a] -> Bool elemList _ [] = False elemList x (y:ys) = x == y || elemList x ys Main> False Main> True Main> False Main> True Main> 31-Dec-10 True

elemList 15 [1,3..10] elemList 15 [1,3..20] elemList False [True, True, True] elemList [] [[3,4], [], [2..8]] elemList [1..3] Fundamentals [[],[1],[1,2],[1,2,3],[1,2,3,4]] Programming - 11 © Pedro Guerreiro

9

Order

• Function minimumList uses function min, which is based on operator [a] -> a minimumList [x] = x minimumList (x:xs) = min x (minimumList xs) Main> minimumList 2 Main> minimumList False Main> minimumList 0.363636363636364 Main> minimumList [2,6,1] Main> minimumList []

31-Dec-10

[5,8,2,9] [True, True, False, True, False] [1/2, 2/5, 3/8, 4/11, 5/7] [[5,3,1], [2,7], [2,6,1], [7]] [[1..3], [2..8], [], [0..100], [0]]


10

Liberty • Functions such as length, take, drop, that do not “inspect” the values of the elements of the lists, use unconstrained polymorphism. takeList :: Int -> [a] -> [a] takeList (x+1) (y:ys) = y : takeList x ys takeList _ _ = [] dropList :: Int -> [a] -> [a] dropList (x+1) (y:ys) = dropList x ys dropList _ ys = ys 31-Dec-10

Liberty: Immunity from arbitrary exercise of authority. Freedom: The power to act or speak or think without externally imposed restraints. (WordWeb, http://wordweb.info.)


11

Polymorphic sorting • We can program quicksort for lists of any type, so long as they are an instance of class Ord. qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort ps ++ zs ++ qsort qs where ps = small x xs Functions small, equal, large must also be programmed zs = equal x (x:xs) polymorphically. See next page. qs = large x xs Main> qsort [5,2,8,5,3,8,5,6,1,8,9,4] [1,2,3,4,5,5,5,6,8,8,8,9] Main> qsort [True, True, False, True, False] [False,False,True,True,True] Main> qsort [1/2, 2/5, 3/8, 4/11, 5/7] [0.363636363636364,0.375,0.4,0.5,0.714285714285714] Main> qsort [[2,4,1], [2,3,4,5],[],[3],[4,1],[3,6,1,2]] 31-Dec-10 Programming Fundamentals - 11 © Pedro Guerreiro [[],[2,3,4,5],[2,4,1],[3],[3,6,1,2],[4,1]]

12

Polymorphic small, large, equal small :: Ord a => a -> [a] -> [a] small _ [] = [] small x (y:ys) | y < x = y : small x ys | otherwise = small x ys large :: Ord a => a -> [a] -> [a] large _ [] = [] large x (y:ys) | y > x = y : large x ys | otherwise = large x ys equal :: Eq a => a -> [a] -> [a] equal _ [] = [] equal x (y:ys) | x == y = y : equal x ys 31-Dec-10 Programming Fundamentals - 11 © Pedro Guerreiro | otherwise = equal x ys

13

Polymorphic unique • Function unique, which removes duplicates, is a general useful function. We must have a polymorphic version, always at hand. unique :: Eq a => [a] -> [a] unique [x] = [x] unique (x1:x2:xs) | x1 /= x2 = x1 : unique (x2:xs) | otherwise = unique (x2:xs) unique _ = []

In this context, removing duplicates means replacing each sequence of equal elements within the list by just one element with the same value. If the list is sorted, all equal elements appear together, and, after unique, only one of each remains.

Main> unique [1,1,1,4,4,5,6,7,7,7,9] [1,4,5,6,7,9] Main> unique [True, False, False, False, True, False, False] [True,False,True,False] Main> unique [[1,2],[1,2],[1,2,3],[1,2,4],[1,2,4]] [[1,2],[1,2,3],[1,2,4]] 31-Dec-10 Programming Fundamentals - 11 © Pedro Guerreiro 14 Main>

Insertionsort • Insertion sort is another interesting sorting algorithm: in order to sort a list, first we sort its tail, then we insert the head in the sorted tail, in the first position such that the tail remains sorted: isort :: Ord a => [a] -> [a] isort [] = [] isort (x:xs) = insert x (isort xs) 31-Dec-10


15

Insertion in a sorted list • This is another one of those algorithms that are simpler to program that to describe in natural language: insert :: Ord a => a -> [a] -> [a] Main> isort [6,1,8,3,4,5,1] insert x [] = [x] [1,1,3,4,5,6,8] Main> insert 5 [2,4,6,8] insert x (y:ys) [2,4,5,6,8] Main> insert 2 [1,2,3,4,5] | x qsortDown [4,2,6,3,5,2,8,6,6,7] [8,7,6,6,6,5,4,3,2,2] Main> isortDown [4,2,6,3,5,2,8,6,6,7] [8,7,6,6,6,5,4,3,2,2]

qsortDown :: Ord a => [a] -> [a] qsortDown [] = [] qsortDown (x:xs) = qsortDown qs ++ zs ++ qsortDown ps where insertDown :: Ord a => a -> [a] -> [a] ps = small x xs zs = equal x (x:xs) insertDown x [] = [x] insertDown x (y:ys) qs = large x xs | x >= y = x:y:ys | otherwise = y: insertDown x ys

31-Dec-10

isortDown :: Ord a => [a] -> [a] isortDown [] = [] Programming Fundamentals - 11 © Pedro Guerreiro isortDown (x:xs) = insertDown x (isortDown xs)

17

Strings are lists of chars • Hence, all the polymorphic functions that we considered can be used for Strings, except those constrained to numeric types (such as sumList): Main> minimumList "robalo" 'a' Main> elemList 'x' "carapau" False Main> lengthList "vila real de santo antonio" 26 Main> head "lisboa" Main> takeList 3 "setubal" 'l' "set" Main> tail "faro" Main> dropList 7 "castro marim" "aro" "marim" Main> 'a' : "parelho" Main> qsort "rodovalho" "aparelho" "adhlooorv" Main> "porta" ++ "legre" Main> unique "AAACCGTTAATCTGGGT" "portalegre" "ACGTATCTGT" Main> isort "castelo branco" 31-Dec-10 Programming Fundamentals - 11 © Pedro Guerreiro 18 " aabccelnoorst"

Problem: anagrams • Given two words, decide whether they are anagrams of each other, i.e., whether they are written with exactly the same letters: anagrams :: Ord a => [a] −> [a] −> Bool anagrams xs ys = qsort xs == qsort ys Main> True Main> True Main> False Main> True Main> True Main> 31-Dec-10 False

anagrams "almirante" "alimentar" anagrams "corpo" "porco" anagrams "rumor" "muro"

The problem is stated in terms of string, but since we programmed polymorphically, we were able to use the function for other types of lists.

anagrams [1,3..9] [9,7..1] anagrams [[3,5],[6],[],[4,44]] [[],[6],[4,44],[3,5]] anagrams [[3,5],[6],[],[4,44]] [[],[6],[44,4],[3,5]] Programming Fundamentals - 11 © Pedro Guerreiro

19

Exercises • Go through the functions in the lists of exercises, and program them polymorphically, whenever it makes sense. • Program a function insertBefore that insert a object x just before the first occurrence of an element with value y in a list zs. • Program a function to check whether two strings have the same characters, irrespective of the number of occurrences of each character. • Program a function to check whether two strings are anagrams, not counting spaces and punctuation. 31-Dec-10


20

Control • Which type classes have we met today? • When computing the average of a list, the list elements must be of a type which is an instance of which class? • Which is the best general purpose sorting algorithm: quicksort or insertionsort? Which of the two is simpler to program? • Which is the minimum list, i.e., the list that is less than any other list? And which is the maximum list? ;-) • Which is less: [1..100000] or [2]? • What are anagrams? 31-Dec-10


21

Tomorrow • We move on to pairs and lists of pairs. • Lists of pairs are very important, because with them we can model key-value tables, which are very common in programming.

31-Dec-10


22