هسکل (۴)

هسکل (۴)

اسلاید 1: Lecture 10 Polymorphism, Overloading and Higher Order Functions1Polymorphism and Overloading

اسلاید 2: Lecture 10 Polymorphism, Overloading and Higher Order Functions2[1,2,3,4,5,6] :: [Integer]Prelude> [a,b,c]++[d,e,f]abcdef :: [Char]Prelude> abc++defabcdef :: [Char]Prelude> [abc,def,ghi]++[uvw,xyz][abc,def,ghi,uvw,xyz] :: [[Char]]What is the type of ++ :[a] -> [a] -> [a] Prelude> [1,2,3] ++ [4,5,6]

اسلاید 3: Lecture 10 Polymorphism, Overloading and Higher Order Functions3lengthList (x:xs) = 1 + lengthList xsMain> lengthList [a,b,c]3 :: IntegerMain> lengthList [1,2,3,4,5,6]6 :: IntegerMain> lengthList [[a,b,c],[d,e,f],[g],[h,i]]4 :: IntegerMain> lengthList [abc,def]2 :: IntegerWhat is the type of lengthList?[a] -> IntlengthList [ ] = 0

اسلاید 4: Lecture 10 Polymorphism, Overloading and Higher Order Functions4In polymorphism type variables are used, as in:[a] -> [a] -> [a] [a] -> Int(a,b) -> [a] Polymorphism: “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 is applied to. The variable a stands for an arbitrary type. Of course all the a’sin the first declaration above stand for the same type wheras in the third, a and b can be different types.

اسلاید 5: Lecture 10 Polymorphism, Overloading and Higher Order Functions5Overloading is another mechanism for using the same function name on different types. ‘a’ = = ‘b’ (a,b) = = (c,d)would require different definitions of “= =“.(a = = c) && (b = = d)An overloaded function has different definitions for different types.

اسلاید 6: Lecture 10 Polymorphism, Overloading and Higher Order Functions6Higher Order Functions

اسلاید 7: Lecture 10 Polymorphism, Overloading and Higher Order Functions7When 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 restPrelude> 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]map: apply to allA higher order function takes a function as an argument or returns a function as a result.

اسلاید 8: Lecture 10 Polymorphism, Overloading and Higher Order Functions8 map :: ( a -> b) -> [a] -> [b]Elements of the list to which the function is appliedElements of the output list that the function returnsType of map:input function input list output list

اسلاید 9: Lecture 10 Polymorphism, Overloading and Higher Order Functions9A function which doubles 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) double :: Int -> Intdouble 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:

اسلاید 10: Lecture 10 Polymorphism, Overloading and Higher Order Functions10A function that returns a list of factorials of all the numbers in a given list of integers: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 each element.fact :: Int -> Intfact n = product [1..n] factAll :: [Int] -> [Int] factAll [ ] = [ ] factAll (first : rest) = (fact first) : (factAll rest)

اسلاید 11: Lecture 10 Polymorphism, Overloading and Higher Order Functions11double :: Int -> Int double n = n*2square :: 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]

اسلاید 12: Lecture 10 Polymorphism, Overloading and Higher Order Functions12Alternatively, 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 listMain> factAll2 [1,2,3,4][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]

اسلاید 13: Lecture 10 Polymorphism, Overloading and Higher Order Functions13We could even have used the built-in function map: doubleAll = map double where double x = 2*xMain> doAll double [1,2,3,4][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][1,4,9,16]Main> doubleAll [1,2,3][2,4,6]

اسلاید 14: Lecture 10 Polymorphism, Overloading and Higher Order Functions14map:: (Int -> Int) -> ([Int] -> [Int]) -- “->”is right 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] factAll3 = map factMain> squareAll3 [1,2,3,4,5][1,4,9,16,25] :: [Int]We can think of map as a function which takes a function of type Int -> Int and returns a function of type [Int] -> [Int] or:

اسلاید 15: Lecture 10 Polymorphism, Overloading and Higher Order Functions15Function 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 write a function that removes all even or odd elements or elements that satisfy a certain condition. removeOdd [ ] = [ ]removeOdd (first:rest) = if odd first then removeOdd rest else first : removeOdd restMain> removeOdd [1,2,3,4,5,6][2,4,6]Filtering

اسلاید 16: Lecture 10 Polymorphism, Overloading and Higher Order Functions16removeEven [ ]=[ ]removeEven (first : rest)= if even first then removeEven rest else first : removeEven restWe can write a general function that does all of these. removeAll p [ ] = [ ] removeAll p (first : rest) = if p first then removeAll p rest else first : removeAll p restMain> removeEven [1,2,3,4,5,6][1,3,5]

اسلاید 17: Lecture 10 Polymorphism, Overloading and Higher Order Functions17Main> 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]

اسلاید 18: Lecture 10 Polymorphism, Overloading and Higher Order Functions18filter :: ( a -> Bool) -> [a] -> [a]The property is a function that returns a BoolElements of the input list, the output list that the function returns and the type that the property works onType of filter: input function input list output list

اسلاید 19: Lecture 10 Polymorphism, Overloading and Higher Order Functions19Definition of filterFortunately, 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 lcaseLetters s = map toLower (filter isAlpha s)An Example: