Higher-Order FunctionsCurrying RevisitedCurrying Revisitedldots Currying Revisitedldots Currying Revisitedldots Patterns of ComputationThe { t map} FunctionThe { t map} Functionldots The { t map} Functionldots The { t map} Functionldots The { t filter} FunctionThe { t filter} Functionldots The { t filter} Functionldots The { t filter} Functionldots { t fold} Functions{ t fold} Functionsldots { t fold} Functionsldots { t fold} Functionsldots { t fold} Functionsldots { t fold} Functionsldots Operator SectionsOperator Sectionsldots { t takeWhile} & { t dropWhile}{ t takeWhile} & { t dropWhile}ldots { t takeWhile} & { t dropWhile}ldots SummarySummaryldots HomeworkHomeworkHomeworkldots Homework520—Spring 2005—16CSc 520Principles of ProgrammingLanguages16: Haskell — Higher-Order FunctionsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—16Higher-Order FunctionsA function is Higher-Order if it takes a function as anargument or returns one as its result.Higher-order function aren’t weird; the differentiationoperation from high-school calculus is higher-order:deriv :: (Float->Float)->Float->Floatderiv f x = (f(x+dx) - f x)/0.0001Many recursive functions share a similar structure. Wecan capture such “recursive patterns” in a higher-orderfunction.We can often avoid the use of explicit recursion byusing higher-order functions. This leads to functionsthat are shorter, and easier to read and maintain.[2]520—Spring 2005—16Currying RevisitedWe have already seen a number of higher-orderfunctions. In fact, any curried function is higher-order.Why? Well, when a curried function is applied to one ofits arguments it returns a new function as the result.Uh, what was this currying thing?A curried function does not have to be applied to all itsarguments at once. We can supply some of thearguments, thereby creating a new specialized function.This function can, for example, be passed as argumentto a higher-order function.[3]520—Spring 2005—16Currying Revisited...How is a curried function defined?A curried function of n arguments (of typest1, t2, · · · , tn) that returns a value of type t is definedlike this:fun :: t1-> t2-> · · · -> tn-> tThis is sort of like defining n different functions (one foreach->). In fact, we could define these functionsexplicitly, but that would be tedious:fun1:: t2-> · · · -> tn-> tfun1a2· · · an= · · ·fun2:: t3-> · · · -> tn-> tfun2a3· · · an= · · ·[4]520—Spring 2005—16Currying Revisited...Duh, how about an example?Certainly. Lets define a recursive function get nth nxs which returns the n:th element from the list xs:get nth 1 (x: ) = xget nth n ( :xs) = get nth (n-1) xsget nth 10 "Bartholomew" ⇒ ’e’Now, let’s use get nth to define functionsget second, get third, get fourth, andget fifth, without using explicit recursion:get second = get nth 2get third = get nth 3get fourth = get nth 4get fifth = get nth 5[5]520—Spring 2005—16Currying Revisited...get fifth "Bartholomew" ⇒ ’h’map (get nth 3)["mob","sea","tar","bat"] ⇒"bart"So, what’s the type of get second?Remember the Rule of Cancellation?The type of get nth is Int -> [a] -> a.get second applies get nth to one argument. So, toget the type ofget second we need to cancelget nth’s first type: Int\\\ -> [a] -> a ≡ [a] -> a.[6]520—Spring 2005—16Patterns of ComputationMappingsApply a function f to the elements of a list L to make anew list L0. Example: Double the elements of an integerlist.SelectionsExtract those elements from a list L that satisfy apredicatep into a new list L0. Example: Extract the evenelements from an integer list.FoldsCombine the elements of a list L into a single elementusing a binary functionf. Example: Sum up theelements in an integer list.[7]520—Spring 2005—16The map Functionmap takes two arguments, a function and a list. mapcreates a new list by applying the function to eachelement of the input list.map’s first argument is a function of type a -> b. Thesecond argument is a list of type[a]. The result is a listof type[b].map :: (a -> b) -> [a] -> [b]map f [ ] = [ ]map f (x:xs) = f x : map f xsWe can check the type of an object using the :typecommand. Example: :type map.[8]520—Spring 2005—16The map Function...map :: (a -> b) -> [a] -> [b]map f [ ] = [ ]map f (x:xs)= f x : map f xsinc x = x + 1map inc [1,2,3,4]⇒ [2,3,4,5]map[2,3,4,5][1,2,3,4]inc[inc 1,inc 2,inc 3,inc 4][9]520—Spring 2005—16The map Function...map :: (a -> b) -> [a] -> [b]map f [ ] = [ ]map f (x:xs) = f x : map f xsmap f [ ] = [ ] means: “The result of applying the function f tothe elements of an empty list is the empty list.”map f (x:xs) = f x : map f xs means: “applying f to the list(x:xs) is the same as applying f to x (the firstelement of the list), then applyingf to the list xs, andthen combining the results.”[10]520—Spring 2005—16The map Function...Simulation:map square [5,6] ⇒square 5 : map square [6] ⇒25 : map square [6] ⇒25 : (square 6 : map square [ ]) ⇒25 : (36 : map square [ ]) ⇒25 : (36 : [ ]) ⇒25 : [36] ⇒[25,36][11]520—Spring 2005—16The filter FunctionFilter takes a predicate p and a list L as arguments. Itreturns a listL0consisting of those elements from L thatsatisfyp.The predicate p should have the type a -> Bool,where a is the type of the list elements.Examples:filter even [1..10] ⇒ [2,4,6,8,10]filter even (map square [2..5]) ⇒filter even [4,9,16,25] ⇒ [4,16]filter gt10 [2,5,9,11,23,114]where gt10 x = x > 10⇒ [11,23,114][12]520—Spring 2005—16The filter Function...We can define filter using either recursion or listcomprehension.Using recursion:filter :: (a -> Bool) -> [a] -> [a]filter [] = []filter p (x:xs)| p x = x : filter p xs| otherwise = filter p xsUsing list comprehension:filter :: (a -> Bool) -> [a] -> [a]filter p xs = [x | x <- xs, p x][13]520—Spring 2005—16The filter Function...filter :: (a->Bool)->[a]->[a]filter [] = []filter p (x:xs)| p x = x : filter p xs| otherwise = filter p xsfilter even [1,2,3,4] ⇒ [2,4][even 1, even 2,even 3, even 4][False, True,False, True][1,2,3,4]evenfilter[2,4][14]520—Spring 2005—16The filter Function...doublePos doubles the positive integers in a list.getEven :: [Int] -> [Int]getEven xs = filter even xsdoublePos :: [Int] -> [Int]doublePos xs = map dbl (filter pos xs)where dbl x = 2 * xpos x = x > 0Simulations:getEven [1,2,3] ⇒ [2]doublePos
View Full Document
Unlocking...