هسکل (4)

صفحه 1:
Polymorphism and Overloading Lecture 10 Polymorphism, Overloading ae ae 

صفحه 2:
-relude> [1,2,3] ++ [4,5,6] [1,2,3,4,5,6] :: [Integer] Prelude> [‘a','b','c']++I['d','e','f] "abcdef" :: [Char] Prelude> "abc"++"def" "abcdef" :: [Char] Prelude> ["abc","def","ghi"]++["uvw","xyz"] ["abc","def","ghi","uvw","xyz"] :: [[Char]] What is the type of ++: [a] -> [a] -> [a] Lecture 10 Polymorphism, Hi 

صفحه 3:
lengthList [ ] = 0 lengthList (x:xs) = 1 + lengthList xs Main> lengthList ['a','b','c'] 3 :: Main> lengthList [1,2,3,4,5,6] 6 :: Integer Main> lengthList [['a','b','c'L['d''e!,'f 1, ['g' L('h7']] 4 :: Integer Main> lengthList ["abc","def"] 2 :: What is the type of lengthList? [a] -> Int Lecture 10 Polymorphism, Overloading figher Dane its ‏هر‎ 

صفحه 4:
olymorphism: “has many shapes”. A function is polymorphic if it can operate on many different types. In polymorphism, the same function definition is used for all the types it 9 type variables are used, as in: is ap to. [a] -> [a] -> [a] [a] -> Int (a,b) -> [a] The variable a stands for an arbitrary type. Of course all the a’s in the first declaration above stand for the same type wheras in the Lecture 10 Polymorphism, 4 loading and Higher ۹ ‏ای اس ام هه ی‎ 

صفحه 5:
Overloading is another mechanism for using the same function name on different types. overloaded function has different definitions for different t ‏م‎ (a,b) = = (c,d) would require different definitions of “= =". (a:='= C) Sb(D— — 0) Lecture 10 Polymorphism, 5 Overloading and Higher ‎kn‏ سد ردن 

صفحه 6:
Higher Order Functions Lecture 10 Polymorphism, Overloading ae ee 

صفحه 7:
her order function takes a function as an argument or retul ion as a result. When we apply a function to all elements of a list, we say that we have mapped that function into the list. There is a Haskell built-in function called map that is used for this purpose. map f list =[f x|x <- list] map f []=[] 20 (first-rest) =f first: map f rest [6,24,120] Lecture 10 Polymorphism, 5 Overloading and Higher TRS A Ses Lele) eae ‏سد ردن‎ kn 

صفحه 8:
Type of map: input function input list output list map ::(a->b) -> [a], [b] \ Elements of the list to \ which the function is Elements of applied the output list that the function returns Lecture 10 Polymorphism, dH 

صفحه 9:
A function which doubles all the values in a list of integers: double :: Int -> Int double n = n*2 doubleAll :: [Int] -> [Int] doubleAll []=[] doubleAll (first:rest) = (double first) : CLOUD 1G ATL 1 SG Jiao ec ‏که‎ a SU IA IIE A function that squares all the values in a list of integers: square :: Int -> Int square n=n“2 squareAll :: [Int] -> [Int] squareAll []=[] squareAll (first : rest) = (square first) : (squareAll rest) PEE 

صفحه 10:
A function that returns a list of factorials of all the numbers in a given list of integers: fact :: Int -> Int fact n = product [1..n] factAll :: [Int] -> [Int] factAll[]=[] factAll (first : rest) = (fact first) : (factAll rest) There is a pattern that is repeated in all these definitions. Here is where we can use a higher order function. We may write a general function: doAll :: (Int -> Int) -> [Int] -> [Int] doAll f []=[] doAll f (first : rest) = (f first ) : (doAll f rest) All we need is this one general definition and the definitions of each of the functions to be applied to 5 Lecture 10 Polymorphism, each element. Overloading ‎ths‏ ا ‎ ‎ ‎ ‎ ‎ 

صفحه 11:
double :: Int -> Int double n = n*2 square :: Int -> Int square n=n“2 fact :: Int -> Int fact n = product [1..n] doAll :: (Int -> Int) -> [Int] -> [Int] doAll f []=[] doAll f (first : rest) = (f first ) : (doAll f rest) 11 

صفحه 12:
Alternatively, we could define all the functions in one line each using our higher order function doAll: doubleAll2 :: [Int] -> [Int ] doubleAll2 list = doAll double list squareAll2 :: [Int] -> [Int ] squareAll2 list = doAll square list factAll2 :: [Int] -> [Int ] factAll2 list = doAll fact list Lecture 10 Polymorphism, 12 Overloading figher ‏نز رین‎ 

صفحه 13:
We could even have used the built-in function map: doubleAll = map double} Main> doAll double [1,2,3,4] where double x = 2)[2,4,6,8] Main> map double [1,2,3,4] [2,4,6,8] Main> doAll fact [1,2,3,4] [1,2,6,24] Main> map fact [1,2,3,4] [1,2,6,24] Main> doAll square [1,2,3,4] [1,4,9,16] :: [Int] Main> map square [1,2,3,4] Lecture 104[1,4,9,16] Overloadin| eA ee as Ade 

صفحه 14:
We can think of map as a function which takes a function of type ۱ ‏ار ی‎ Unt] -» Lind ht associative So, we can define the following functions which return a doubleAll3 :: [Int] -> [Int ] squareAll3 :: [Int] -> [Int] factAll3 - = = map fact Lecture 10 Polymorphism, 14 Overloading ‏ا‎ ths 

صفحه 15:
Filtering Function remove (removes an element from a list): remove []=[] remove element (first : rest) = if element = = first then remove element rest else first : (remove element rest) ‘We may want to wr} a function that rem| all even or odd ele removeOdd (first:rest) = if odd first then removeOdd or elements that safj a certain condition, else first : 

صفحه 16:
Main> removeEven [1,2,3,4,5,6] OVveEven [ ]=[ ] removeEven (first : rest)= if even first then removeEven rest e can write a generaléunction that does all of these. removeAll p []=[] removeAll p (first: rest) = if p first then removeAll p 25 16 else first: 

صفحه 17:
Main> removeAll odd [1,2,3,4,5,6] [2,4,6] Main> removeAll even <عضع]ژ2ع_سط_ )11,2,3,4,5,6 [1,3,5] We could have used filter to do all this rather than defining removeAll. This is another useful built-in function. It takes a property and a list and returns a list ts that have that property. [2,4,6] Lecture 10 Polymorphism, 17 Overloading andi eho 

صفحه 18:
output list a-> Bool) -> [a] - Elements of the input list, the output list that the function returns and the type that the property works input list Type of filter: input function filter :: > fal | The property is a function that returns a Bool Lecture 10 Polym8:Bhism, 18 

صفحه 19:
Definition of filter Fortunately, filter is a built-in function. If it wasn’t a built-in function, we could have defined filter as follows. filter :: (Int -> Bool) -> [Int] -> [Int] filter p []= [] filter p (first : rest) = if (p first) then first : (filter p rest) else filter p rest An Example: IcaseLetters ‏و‎ = map toLower (filter isAlpha s) Lecture 10 Polymorphism, 19 Overloading ‏ا‎ ths 

Polymorphism and Overloading Lecture 10 Polymorphism, Overloading and Higher 1 Prelude> [1,2,3] ++ [4,5,6] [1,2,3,4,5,6] :: [Integer] Prelude> ['a','b','c']++['d','e','f'] "abcdef" :: [Char] Prelude> "abc"++"def" "abcdef" :: [Char] Prelude> ["abc","def","ghi"]++["uvw","xyz"] ["abc","def","ghi","uvw","xyz"] :: [[Char]] What is the type of ++ : [a] -> [a] -> [a] Lecture 10 Polymorphism, Overloading and Higher 2 lengthList [ ] = 0 lengthList (x:xs) = 1 + lengthList xs Main> lengthList ['a','b','c'] 3 :: Integer Main> lengthList [1,2,3,4,5,6] 6 :: Integer Main> lengthList [['a','b','c'],['d','e','f'],['g'],['h','i']] 4 :: Integer Main> lengthList ["abc","def"] 2 :: Integer What is the type of lengthList? [a] -> Int Lecture 10 Polymorphism, Overloading and Higher 3 olymorphism: “has many shapes”. A function is polymorphic if it can operate on many different types. In polymorphism, the same function definition is used for all the types it polymorphism type variables are used, as in: is applied to. [a] -> [a] -> [a] [a] -> Int (a,b) -> [a] The variable a stands for an arbitrary type. Of course all the a’s in the first declaration above stand for the same type wheras in the Lecture 10 Polymorphism, 4 Overloading and Higher Overloading is another mechanism for using the same function name on different types. n overloaded function has different definitions for different t ‘a’ = = ‘b’ (a,b) = = (c,d) would require different definitions of “= =“. (a = = c) && (b = = d) Lecture 10 Polymorphism, Overloading and Higher 5 Higher Order Functions Lecture 10 Polymorphism, Overloading and Higher 6 her order function takes a function as an argument or retur ion as a result. When we apply a function to all elements of a list, we say that we have mapped that function into the list. There is a Haskell built-in function called map that is used for this purpose. map f list = [ f x | x <- list] map f [ ] = [ ] map f (first:rest) = f first : map f rest Prelude> map odd [1,2,3,4,5] [True,False,True,False,True] Prelude> map (^2) [1,2,3] [1,4,9] Fact> map fact [3,4,5] [6,24,120] Lecture 10 Polymorphism, Overloading and Higher 7 Type of map: input function input list output list map :: ( a -> b) -> [a] -> [b] Elements of the list to which the function is applied Elements of the output list that the function returns Lecture 10 Polymorphism, Overloading and Higher 8 A function which doubles all the values in a list of integers: double :: Int -> Int double n = n*2 doubleAll :: [Int] -> [Int] doubleAll [ ] = [ ] doubleAll (first:rest) = (double first) : (doubleAll rest) A function that squares all the values in a list of integers: square :: Int -> Int square n = n^2 squareAll :: [Int] -> [Int] squareAll [ ] = [ ] squareAll (first : rest) = (square first) : (squareAll rest) Lecture 10 Polymorphism, 9 Overloading and Higher A function that returns a list of factorials of all the numbers in a given list of integers: fact :: Int -> Int fact n = product [1..n] factAll :: [Int] -> [Int] factAll [ ] = [ ] factAll (first : rest) = (fact first) : (factAll rest) There is a pattern that is repeated in all these definitions. Here is where we can use a higher order function. We may write a general function: doAll :: (Int -> Int) -> [Int] -> [Int] doAll f [ ] = [ ] doAll f (first : rest) = (f first ) : (doAll f rest) All we need is this one general definition and the definitions of each of the functions to be applied to Lecture 10 Polymorphism, 10 each element. Overloading and Higher double :: Int -> Int double n = n*2 square :: Int -> Int square n = n^2 fact :: Int -> Int fact n = product [1..n] doAll :: (Int -> Int) -> [Int] -> [Int] doAll f [ ] = [ ] doAll f (first : rest) = (f first ) : (doAll f rest) Main> doAll double [1,2,3,4] [2,4,6,8] Main> doAll fact [1,2,3,4] [1,2,6,24] Main> doAll square [1,2,3,4] [1,4,9,16] Lecture 10 Polymorphism, Overloading and Higher 11 Alternatively, we could define all the functions in one line each using our higher order function doAll: doubleAll2 :: [Int] -> [Int ] doubleAll2 list = doAll double list squareAll2 :: [Int] -> [Int ] squareAll2 list = doAll square list Main> factAll2 [1,2,3,4] factAll2 :: [Int] -> [Int ] factAll2 list = doAll fact list [1,2,6,24] Main> doubleAll2 [1,2,3,4] [2,4,6,8] Main> doAll square [1,2,3,4 [1,4,9,16] Lecture 10 Polymorphism, Overloading and Higher 12 We could even have used the built-in function map: doubleAll = map double Main> doAll double [1,2,3,4] [2,4,6,8] where double x = 2*x Main> doubleAll [1,2,3] [2,4,6] Main> map double [1,2,3,4] [2,4,6,8] Main> doAll fact [1,2,3,4] [1,2,6,24] Main> map fact [1,2,3,4] [1,2,6,24] Main> doAll square [1,2,3,4] [1,4,9,16] :: [Int] Main> map square [1,2,3,4] Lecture 10 Polymorphism, [1,4,9,16] Overloading and Higher 13 We can think of map as a function which takes a function of type Int -> Int and returns a function of type [Int] -> [Int] map:: (Int -> Int) -> ([Int] -> [Int]) -- “->”is right or: associative So, we can define the following functions which return a function as their result: doubleAll3 :: [Int] -> [Int ] doubleAll3 = map double squareAll3 :: [Int] -> [Int] squareAll3 = map square factAll3 :: [Int] -> [Int] Main> squareAll3 [1,2,3,4,5] factAll3 = map fact [1,4,9,16,25] :: [Int] Lecture 10 Polymorphism, Overloading and Higher 14 Filtering Function remove (removes an element from a list): remove _ [ ] = [ ] remove element (first : rest) = if element = = first then remove element rest else first : (remove element rest) Main> removeOdd We may want to write [1,2,3,4,5,6] a function that removes [2,4,6] removeOdd [ ] = [ ] all even or odd elements removeOdd (first:rest) or elements that satisfy = if odd first a certain condition. rest Lecture 10 Polymorphism, Overloading and Higher then removeOdd else first : 15 Main> removeEven [1,2,3,4,5,6] [1,3,5] removeEven [ ]=[ ] removeEven (first : rest)= if even first then removeEven rest We can write a general function that does all of these. else first : removeEven removeAll prest []=[] removeAll p (first : rest) = if p first then removeAll p rest Lecture 10 Polymorphism, Overloading and Higher else first : 16 Main> removeAll odd [1,2,3,4,5,6] [2,4,6] Main> removeAll even [1,2,3,4,5,6] [1,3,5] We could have used filter to do all this rather than defining removeAll. This is another useful built-in function. It takes a property and a list and returns a list containing the elements that have that property. Main> filter odd [1,2,3,4,5,6] [1,3,5] Main> filter even [1,2,3,4,5,6,7] [2,4,6] Lecture 10 Polymorphism, Overloading and Higher 17 Type of filter: input function input list output list filter :: ( a -> Bool) -> [a] -> [a] The property is a function that returns a Bool Elements of the input list, the output list that the function returns and the type that the property works on Lecture 10 Polymorphism, Overloading and Higher 18 Definition of filter Fortunately, filter is a built-in function. If it wasn’t a built-in function, we could have defined filter as follows. filter :: (Int -> Bool) -> [Int] -> [Int] filter p [ ] = [ ] filter p (first : rest) = if (p first) then first : (filter p rest) else filter p rest An Example: lcaseLetters s = map toLower (filter isAlpha s) Lecture 10 Polymorphism, Overloading and Higher 19