Higher-Order FunctionsHigher-Order Functions: { t map}Higher-Order Functions: { t map}ldots Higher-Order Functions: { t map}ldots Higher-Order Functions: { t map}ldots Higher-Order Functions: { t map}ldots Lambda ExpressionsHigher-Order Functions: { t map}ldots Higher-Order Functions: { t filter}Higher-Order Functions: { t fold}Higher-Order Functions: { t fold}ldots Higher-Order Functions: { t fold}520—Spring 2005—8CSc 520Principles of ProgrammingLanguages8: Scheme — Higher-Order FunctionsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—8Higher-Order FunctionsA function is higher-order if1. it takes another function as an argument, or2. it returns a function as its result.Functional programs make extensive use ofhigher-order functions to make programs smaller andmore elegant.We use higher-order functions to encapsulate commonpatterns of computation.[2]520—Spring 2005—8Higher-Order Functions: mapMap a list of numbers to a new list of their absolutevalues.Here’s the definition of abs-list from a previouslecture:(define (abs-list L)(cond[(null? L) ’()][else (cons (abs (car L))(abs-list (cdr L)))]))> (abs-list ’(1 -1 2 -3 5))(1 1 2 3 5)[3]520—Spring 2005—8Higher-Order Functions: map...This type of computation is very common.Scheme therefore has a built-in function(map f L)which constructs a new list by applying the function f toevery element of the list L.(map f ’(e1e2e3e4))⇓((f e1) (f e2) (f e3) (f e4)))[4]520—Spring 2005—8Higher-Order Functions: map...map is a higher-order function, i.e. it takes anotherfunction as an argument.(define (addone a) (+ 1 a))> (map addone ’(1 2 3)(2 3 4)> (map abs ’(-1 2 -3))(1 2 3)[5]520—Spring 2005—8Higher-Order Functions: map...We can easily define map ourselves:(define (mymap f L)(cond[(null? L) ’()][else(cons (f (car L)) (mymap f (cdr L)))]))> (mymap abs ’(-1 2 -3))(1 2 3)[6]520—Spring 2005—8Higher-Order Functions: map...If the function takes n arguments, we give map n lists ofarguments:> (map string-append’("A" "B" "C") ’("1" "2" "3"))("A1" "B2" "C3")> (map + ’(1 2 3) ’(1 2 3))(list 2 4 6)> (map cons ’(a b c) ’((1) (2) (3)))((a 1) (b 2) (c 3))[7]520—Spring 2005—8Lambda ExpressionsA lambda-expression evaluates to a function:(lambda (x) (* x x))xis the function’s formal parameter.Lambda-expressions don’t give the function a name —they’reanonymous functions.Evaluating the function:> ((lambda (x) (* x x)) 3)9[8]520—Spring 2005—8Higher-Order Functions: map...We can use lambda-expressions to constructanonymous functions to pass to map. This saves usfrom having to define auxiliary functions:(define (addone a) (+ 1 a))> (map addone ’(1 2 3)(2 3 4)> (map (lambda (a) (+ 1 a)) ’(1 2 3))(2 3 4)[9]520—Spring 2005—8Higher-Order Functions: filterThe filter-function applies a predicate (boolean-valuedfunction) p to all the elements of a list.A new list is returned consisting of those elements forwhich p returns #t.(define (filter p L)(cond[(null? L) ’()][(p (car L))(cons (car L) (filter p (cdr L)))][else (filter p (cdr L))]))> (filter (lambda (x) (> x 0)) ’(1 -2 3 -4))(1 3)[10]520—Spring 2005—8Higher-Order Functions: foldConsider the following two functions:(define (sum L)(cond[(null? L)0][else (+ (car L) (sum (cdr L)))]))(define (concat L)(cond[(null? L)"" ][else (string-append (car L) (concat (cdr L)))]))> (sum ’(1 2 3))6> (concat ’("1" "2" "3"))"123"[11]520—Spring 2005—8Higher-Order Functions: fold...The two functions only differ in what operations theyapply (+ vs. string-append, and in the value returnedfor the base case (0 vs. "").The fold function abstracts this computation:(define (fold L f n)(cond[(null? L) n][else (f (car L) (fold (cdr L) f n))]))> (fold ’(1 2 3) + 0)6> (fold ’("A" "B" "C") string-append "")"ABC"[12]520—Spring 2005—8Higher-Order Functions: foldIn other words, fold folds a list together bysuccessively applying the functionf to the elements ofthe list L.(apply f ’(e1e2e3e4)) ⇒(f e1(f e2(f
View Full Document
Unlocking...