Transcript Functional

Functional Programming
Concepts
•Creating New Functions
•Composition
•Currying
•Lazy Evaluation
•Polymorphism
CSE 341 -- S. Tanimoto
Functional Programming
1
Composition and Currying in
Functional Languages
Q. How can two functions be combined to create
a new function?
A. By composition. h(x) = g(f(x))
Q. How can a function and one value be
combined to create a new function?
A. By currying.
h(x)
= f(a, x)
h2(x, y) = f2(a, x, y)
CSE 341 -- S. Tanimoto
Functional Programming
2
Composition in Lisp
(defun compose-unary-fns (f g)
#’(lambda (x) (funcall f (funcall g x))) )
(setq tripler #’(lambda (x) (* 3 x)))
(setq squarer #’(lambda (x) (* x x)))
(setq triple-squarer
(compose-unary-fns
tripler
squarer) )
(funcall triple-squarer 5)
=> 75
CSE 341 -- S. Tanimoto
Functional Programming
3
Currying in Lisp
(defun curry-binary-fn (f firstarg)
#’(lambda (x) (funcall f firstarg x)) )
(setq cons-with-john
(curry-binary-fn #’cons ’john) )
(funcall cons-with-john 21)
=> (21 . JOHN)
CSE 341 -- S. Tanimoto
Functional Programming
4
Currying in Miranda
Q. How does Miranda support currying?
A. Any function that takes multiple arguments can be
curried.
mult x y = x * y
triple = mult 3
Here mult is being curried with 3 producing a new
function triple.
Miranda defines a function of n arguments to be
equivalent to a function of one argument that
returns another function, that function taking n-1
arguments.
CSE 341 -- S. Tanimoto
Functional Programming
5
Lazy Evaluation
Q. What is lazy evaluation?
A. It's a policy of only evaluating forms whose values
are needed by a consumer, such as a print request.
If Lisp fully supported lazy evaluation, then
(FIRST (LIST 1 (+ 2 3) (* 4 5) (/ 6 7)))
would not result in any arithmetic actually being
performed, since only the element 1 needs to be
returned.
CSE 341 -- S. Tanimoto
Functional Programming
6
Lazy Evaluation - Lisp?
Q. Does Lisp support lazy evaluation?
A. Only in some limited ways...
The special forms IF and COND, and the macros AND
and OR perform lazy evaluation of their arguments.
(or (= n 2) (= n 3) (= n 5) (= n 7) (= n 11)
‘not-a-small-prime)
If n is 2, then only the first comparison is performed.
CSE 341 -- S. Tanimoto
Functional Programming
7
Lazy Evaluation - Efficiency?
Q. Does lazy evaluation always lead to more efficient
computation?
A. No. Consider the Miranda code
double x = x + x
double 11*13
This evaluates as
11*13 + 11*13 = 143 + 143 = 186
But with applicative order evaluation we would have
double 11*13 = double 143 = 143 + 143 = 186
which performs less arithmetic.
Also, lazy evaluation usually incurs extra overhead.
CSE 341 -- S. Tanimoto
Functional Programming
8
Lazy Evaluation and Infinite
Data Structures
Q. Are there any other benefits of lazy evaluation?
A. Yes, it permits creation and manipulation of
"infinite" data structures.
In Miranda, the list (1, 2, 3, ... ) is written
[1..]
and can be used in expressions.
hd (tl (tl (map triple [1..])))
|| returns 9
If you told Miranda to compute the length of [1..],
however, it would loop indefinitely.
CSE 341 -- S. Tanimoto
Functional Programming
9
Polymorphism
Q. What is polymorphism?
A. The property of a programming language feature
or entity being able to support multiple types of data.
Q. What is usually meant by function polymorphism?
A. The ability for one function to accept arguments
whose types can vary from one call to another.
In Lisp, for example, CONS is polymorphic:
(cons 1 2) ; numeric arguments
(cons t nil) ; symbolic arguments
Note: CONS is not overloaded; it's polymorphic.
CSE 341 -- S. Tanimoto
Functional Programming
10
Polymorphism
Q. Is there another way for a function to exhibit
polymorphism?
A. Yes, it can return different types of values. For
example, the Lisp function given by
(defun check-for-positive (n)
(if (< n 0) 'negative n) )
may return either a number or a symbol, depending
on the value of n.
CSE 341 -- S. Tanimoto
Functional Programming
11
Polymorphic Variables
Q. What is a polymorphic variable?
A. It’s a variable that can hold values of more than
one type.
In Lisp, symbols often serve as polymorphic
variables:
(setq x 5)
(setq x ‘apple)
(setq x ‘(peaches and pears))
CSE 341 -- S. Tanimoto
Functional Programming
12
Polymorphism in Java
Q. Does Java support polymorphism?
A. Yes, via the use of the built-in, general class Object.
public class Widget extends Object {
private String name;
public void setName(String n) {name = n;}
}
public Widget test(Widget w) {
Widget w2 = (Widget) w.clone();
w2.setName(“The cloned Widget”);
return w2;
}
CSE 341 -- S. Tanimoto
Functional Programming
13