DOC PREVIEW
UA CSC 520 - Study Notes

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSc 520 — Principles of Programming Languages39 : Scheme — Higher-Order FunctionsChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergMay 2, 20081 Higher-Order Functions• A 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 of higher-order functions to make programs smaller and moreelegant.• We use higher-order functions to encapsulate common patterns of computation.2 Higher-Order Functions: map• Map a list of numbers to a new list of their absolute values.• Here’s the definition of abs-list from a previous lecture:(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 Higher-Order Functions: map. . .• This type of computation is very common.• Scheme therefore has a built-in function1(map f L)which constructs a new list by applying the function f to every element of the list L.(map f ’(e1e2e3e4))⇓((f e1) (f e2) (f e3) (f e4)))4 Higher-Order Functions: map. . .• map is a higher-order function, i.e. it takes another function 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 Higher-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 Higher-Order Functions: map. . .• If the function takes n arguments, we give map n lists of arguments:> (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))27 Lambda Expressions• A lambda-expression evaluates to a function:(lambda (x) (* x x))x is the function’s formal parameter.• Lambda-expressions don’t give the function a name — they’re anonymous functions.• Evaluating the function:> ((lambda (x) (* x x)) 3)98 Higher-Order Functions: map. . .• We can use lambda-expressions to construct anonymous functions to pass to map. This saves us fromhaving 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 Higher-Order Functions: filter• The filter-function applies a predicate (boolean-valued function) p to all the elements of a list.• A new list is returned consisting of those elements for which 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 Higher-Order Functions: foldConsider the following two functions:3(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 Higher-Order Functions: fold. . .• The two functions only differ in what operations they apply (+ vs. string-append, and in the valuereturned for 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 Higher-Order Functions: fold• In other words, fold folds a list together by successively applying the function fto the elements ofthe list L.(apply f ’(e1e2e3e4)) ⇒(f e1(f e2(f


View Full Document

UA CSC 520 - Study Notes

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?