Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Higher-Order Functions
In Scheme, function is a first-class value (Functions can go wherever expressions go)
• Higher Order Functions
• Function can be used as an argument • Function can be used as a return value
2
Function as Argument Repeat any function twice?
(define (double x) (* x 2))
(define (quad x) (double (double x))
(define (square x) (* x x))
(define (fourth x) (square (square x))
More reusable code
(define (twice f x) (f (f x)))
(twice double 2)
(twice quad 2)
3
Examples w/o Higher-Order Functions Find all numbers > 5 in a list
newlist = empty
foreach (elem in lst)
if (elem > 5)
add elem to newlist
Find all strings in a list
newlist = empty
foreach (elem in lst)
if (elem is String)
add elem to newlist
4
Filter
filter f l: return elements for which f returns #t
5
Examples w Higher-Order Functions
filter f l: return elements for which f returns #t
(filter (lambda (x) (> x 5)) ’(1 4 7 10))
(filter string? ’(1 “1” 2 “2” 3 “3”))
6
Examples w/o Higher-Order Functions Multiple 2 to each element in a list
newlist = empty
foreach (elem in lst)
add elem*2 to newlist
Square each element in a list
newlist = empty
foreach (elem in lst)
add elem*elem to newlist
7
Map
map f l: applies function f to each element of list l
8
Examples w Higher-Order Functions
map f l: applies function f to each element of list l
(map double ’(1 2 3))
(map square ’(1 2 3))
9
Map
In previous lecture, we had:
(define (subs a b lst)
(if (null? lst) ’()
(let ((rest (subs a b (cdr lst))))
(if (equal? (car lst) a)
(cons b rest)
(cons (car lst) rest)))))
Using map, we have
(define (subs a b lst)
(map (lambda (c)
(if (equal? a c) b c))
lst))
10
Map on Multiple Lists
map f l1 l2 l3: applies function f to elements at
the same position of list l1,l2,l3 (with same length) (map + ’(1 2 3) ’(4 5 6) ’(7 8 9))
(map (lambda (x y) (- x y)) ’(1 2 3) ’(4 5 6))
11