Composing FunctionsComposing Functionsldots Composing Functionsldots Composing Functionsldots Example: Splitting LinesPrecedence & AssociativityThe { t count} FunctionThe { t count} Functionldots The { t init} & { t last} FunctionsThe { t any} Function{ t commaint} Revisitedldots { t commaint} Revisitedldots { t commaint} Revisitedldots { t commaint} Revisitedldots { t commaint} Revisitedldots Lambda ExpressionsSummaryHomework520—Spring 2005—17CSc 520Principles of ProgrammingLanguages17: Haskell — Composing FunctionsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—17Composing FunctionsWe want to discover frequently occurring patterns ofcomputation. These patterns are then made into (oftenhigher-order) functions which can bespecialized andcombined. map f L and filter f L can be specializedand combined:double :: [Int] -> [Int]double xs = map ((*) 2) xspositive :: [Int] -> [Int]positive xs = filter ((<) 0) xsdoublePos xs = map ((*) 2) (filter ((<) 0) xs)? doublePos [2,3,0,-1,5][4, 6, 10][2]520—Spring 2005—17Composing Functions...Functional composition is a kind of “glue” that is used to“stick” simple functions together to make more powerfulones.In mathematics the ring symbol (◦) is used to composefunctions:(f ◦ g)(x) = f(g(x))In Haskell we use the dot (".") symbol:infixr 9 .(.) :: (b->c) -> (a->b) -> (a->c)(f . g)(x) = f(g(x))[3]520—Spring 2005—17Composing Functions...(.) :: (b->c) -> (a->b) -> (a->c)(f . g)(x) = f(g(x))gff . gaaccb"." takes two functions f and g as arguments, andreturns a new functionh as result.g is a function of type a->b.f is a function of type b->c.h is a function of type a->c.(f.g)(x) is the same as z=g(x) followed by f(z).[4]520—Spring 2005—17Composing Functions...We use functional composition to write functions moreconcisely. These definitions are equivalent:doit x = f1 (f2 (f3 (f4 x)))doit x = (f1 . f2 . f3 . f4) xdoit = f1 . f2 . f3 . f4The last form of doit is preferred. doit’s arguments areimplicit; it has the same parameters as the composition.doit can be used in higher-order functions (the secondform is preferred):? map (doit) xs? map (f1 . f2 . f3 . f4) xs[5]520—Spring 2005—17Example: Splitting LinesAssume that we have a function fill that splits astring into filled lines:fill :: string -> [string]fill s = splitLines (splitWords s)fill first splits the string into words (usingsplitWords) and then into lines:splitWords :: string -> [word]splitLines :: [word] -> [line]We can rewrite fill using function composition:fill = splitLines . splitWords[6]520—Spring 2005—17Precedence & Associativity1. "." is right associative. I.e.f.g.h.i.j = f.(g.(h.(i.j)))2. "." has higher precedence (binding power) than anyother operator, except function application:5 + f.g 6 = 5 + (f. (g 6))3. "." is associative:f . (g . h) = (f . g) . h4. "id" is "."’s identity element, i.e id . f = f = f. id:id :: a -> aid x = x[7]520—Spring 2005—17The count FunctionDefine a function count which counts the number oflists of length n in a list L:count 2 [[1],[],[2,3],[4,5],[]] ⇒ 2Using recursion:count :: Int -> [[a]] -> Intcount [] = 0count n (x:xs)| length x == n = 1 + count n xs| otherwise = count n xsUsing functional composition:count’ n = length . filter (==n) . map length[8]520—Spring 2005—17The count Function...count’ n = length . filter (==n) . map lengthWhat does count’ do?[1,0,2,2,0]filter (==2)length[2,2]map length[[1],[],[2,3],[4,5],[]]2Note thatcount’ n xs = length (filter (==n) (map length xs))[9]520—Spring 2005—17The init & last Functionslast returns the last element of a list.init returns everything but the last element of a list.Definitions:last = head . reverseinit = reverse . tail . reverseSimulations:[1,2,3]reverse=⇒ [3,2,1]head=⇒ 3[1,2,3]reverse=⇒ [3,2,1]tail=⇒ [2,1]reverse=⇒ [1,2][10]520—Spring 2005—17The any Functionany p xs returns True if p x == True for some x inxs:any ((==)0) [1,2,3,0,5] ⇒ Trueany ((==)0) [1,2,3,4] ⇒ FalseUsing recursion:any :: (a -> Bool) -> [a] -> Boolany[] = Falseany p (x:xs) = | p x = True| otherwise = any p xsUsing composition:any p = or . map p[1,0,3]map ((==)0)=⇒ [False,True,False]or=⇒True[11]520—Spring 2005—17commaint Revisited...Let’s have another look at one simple (!) function,commaint.commaint works on strings, which are simply lists ofcharacters.You are not\\\ now supposed to understand this!From the commaint documentation:[commaint] takes a single string argumentcontaining a sequence of digits, and outputs thesame sequence with commas inserted after everygroup of three digits,· · ·[12]520—Spring 2005—17commaint Revisited...Sample interaction:? commaint "1234567"1,234,567commaint in Haskell:commaint = reverse . foldr1 (\x y->x++","++y) .group 3 . reversewhere group n = takeWhile (not.null) .map (take n).iterate (drop n)[13]520—Spring 2005—17commaint Revisited...group3iterate (drop 3)map (take 3)foldr1 (\x y−>x++","++y)"765,432,1"["765", "432", "1"]takeWhile (not.null)"7654321"["7654321","4321","1","","", ...]["765","432","1","","",...]"1,234,567""1234567"reversereverse[14]520—Spring 2005—17commaint Revisited...commaint = reverse . foldr1 (\x y->x++","++y) .group 3 . reversewhere group n = takeWhile (not.null) .map (take n).iterate (drop n)iterate (drop 3) s returns the infinite list of strings[s, drop 3 s, drop 3 (drop 3 s),drop 3 (drop 3 (drop 3 s)), · · ·]map (take n) xss shortens the lists in xss to nelements.[15]520—Spring 2005—17commaint Revisited...commaint = reverse . foldr1 (\x y->x++","++y) .group 3 . reversewhere group n = takeWhile (not.null) .map (take n).iterate (drop n)takeWhile (not.null) removes all empty stringsfrom a list of strings.foldr1 (\x y->x++","++y) s takes a list of stringss as input. It appends the strings together, inserting acomma in between each pair of strings.[16]520—Spring 2005—17Lambda Expressions(\x y->x++","++y) is called a lambda expression.Lambda expressions are simply a way of writing (short)functions inline. Syntax:\ arguments -> expressionThus, commaint could just as well have been written ascommaint = · · · . foldr1 insert . · · ·where group n = · · ·insert x y = x++","++yExamples:squareAll xs = map (\ x -> x * x) xslength = foldl’ (\n -> n+1) 0[17]520—Spring 2005—17SummaryThe built-in operator "." (pronounced “compose”)takes two functions f and g as
View Full Document
Unlocking...