CSc 520 - Principles of Programming Languages
39 : Scheme -- Higher-Order Functions

Christian Collberg

Department of Computer Science

University of Arizona

1 Higher-Order Functions

• A function is higher-order if
  1. it takes another function as an argument, or
  2. it returns a function as its result.
• Functional programs make extensive use of higher-order functions to make programs smaller and more elegant.
• 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:

1#1

3 Higher-Order Functions: map...

• This type of computation is very common.
• Scheme therefore has a built-in function
  2#2
  which constructs a new list by applying the function f to every element of the list L.
  3#3
  

4 Higher-Order Functions: map...

• map is a higher-order function, i.e. it takes another function as an argument.

4#4

5 Higher-Order Functions: map...

• We can easily define map ourselves:

5#5

6 Higher-Order Functions: map...

• If the function takes 6#6 arguments, we give map 6#6 lists of arguments:

7#7

7 Lambda Expressions

• A lambda-expression evaluates to a function:
  8#8
  x is the function's formal parameter.
• Lambda-expressions don't give the function a name -- they're anonymous functions.
• Evaluating the function:
  9#9
  

8 Higher-Order Functions: map...

• We can use lambda-expressions to construct anonymous functions to pass to map. This saves us from having to define auxiliary functions:

10#10

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.

11#11

10 Higher-Order Functions: fold

Consider the following two functions:

12#12

11 Higher-Order Functions: fold...

• The two functions only differ in what operations they apply (+ vs. string-append, and in the value returned for the base case (0 vs. "").
• The fold function abstracts this computation:

13#13

12 Higher-Order Functions: fold

• In other words, fold folds a list together by successively applying the function f to the elements of the list L.
  14#14