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
Examples w/o Higher-Order Functions Compute the sum of a list
init = 0
foreach (elem in lst)
init += elem
Compute the product of a list
init = 1
foreach (elem in lst)
init *= elem
3
Foldl
foldl f a (e1 e2 en): returns f en(… (f e2(f e1 a)) …)
4
Examples with Higher-Order Functions foldl f a (e1 e2 en): returns
f en(… (f e2(f e1 a)) …)
(foldl + 0 ‘(1 2 3 4 5))
(foldl * 1 ‘(1 2 3 4 5))
5
Foldl
In previous lecture, we had:
(define (lstSum lst)
(if (null? lst) 0
( + (car lst) (lstSum (cdr lst)))))
Using foldl, we have
(define (lstSum lst) (foldl + 0 lst)
6
Examples with Higher-Order Functions
foldl f a (e1 e2 en): returns f en(… (f e2(f e1 a)) …)
(foldl (lambda (x a) (+ a (* x x)))
0 ‘(1 2 3 4 5))
7
Function as Return Value
In Scheme, function is a first-class value (Functions can go wherever expressions go)
• Functions as return values
(define (addN n) (lambda (m) (+ m n)))
((addN 10) 20) (+ 10 20)
(twice (addN 10) 20) (twice (+ 10) 20)
8
Currying and Partial Evaluation
9
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Pass multiple parameters as a list?
(add ’(1 2))
(add 1 2)
add takes 2 parameters
10
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Add 2 to each element in a list?
map f l: applies function f to each element of list l
(map (add 2) ’(1 2 3)) ?
11
Multi-Argument Functions
(define (add m n) (+ m n))
add: Int, Int → Int
Add 2 to each element in a list?
map f l: applies function f to each element of list l
(map (add 2) ’(1 2 3))
add takes two parameters
A multi-argument function can only
be used when all parameters are ready!
12
Currying: Every function is treated as taking at most one parameter
(define (add m n) (+ m n))
add: Int, Int → Int
Curried version
(define (addN n) (lambda (m) (+ m n))
addN: Int → (Int → Int)
also written as: Int → Int → Int (right associative)
13
Uncurried version Curried version
(define (add m n)
(+ m n))
(define (addN n)
(lambda (m) (+ m n))
add: Int, Int → Int
addN: Int → (Int → Int)
(add 2 3) ((addN 2) 3)
Curried form allows partial evaluation
(map (add 2)
’(1 2 3))
(map (addN 2)
’(1 2 3))
14
Currying
Haskell B. Curry Penn State 1929-1966
Outside of McAllister Building
15
Currying
In terms of lambda calculus,
the curried function of 𝜆𝑥!𝑥” … 𝑥#. 𝑒 is 𝜆𝑥!. (𝜆𝑥”. … 𝜆𝑥#. 𝑒 )
(define (curry3 f)
(lambda (x)
(lambda (y)
(lambda (z)
(f x y z)))))
(define (curry2 f)
(lambda (x)
(lambda (y)
(f x y))))
16
Partial Evaluation
A function is evaluated with one or more of the leftmost actual parameters
((curry2 add) 2)is a partial evaluation of add
We can think it as a temporary result, in the form of a function
17
Partial Evaluation
A function is evaluated with one or more of the leftmost actual parameters
(map ((curry2 add) 2) ’(1 2 3))
add: 𝜆𝑥 𝑦. (+ 𝑥 𝑦) curry2add :𝜆𝑥.𝜆𝑦.(+𝑥𝑦)
curry2add 2 :𝜆𝑦.(+2𝑦)
map( curry2add 2) ’ 123 :’ 345
18
Uncurrying
In terms of lambda calculus,
the uncurried function of 𝜆𝑥!. (𝜆𝑥”. … 𝜆𝑥#. 𝑒 ) is 𝜆𝑥!𝑥” …𝑥#.𝑒
(define (uncurry2 f)
(lambda (x y)
((f x) y)))
(define (uncurry3 f)
(lambda (x y z)
(((f x) y) z)))
19