6.01, Spring Semester, 2008—Course notes for Week 2 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS ISpring Semester, 2008Course notes for Week 21 Higher-order functionsAnother element of functional programming style is the idea of functions as first-class objects. Thatmeans that we can treat functions or procedures in much the same way we treat numbers or stringsin our programs: we can pass them as arguments to other procedures and return them as the resultsfrom procedures. This will let us capture important common patterns of abstraction and will alsobe an important element of object-oriented programming.We’ve been talking about the fundamental principles of software engineering as being modularityand abstraction. But another important principle is laziness! Don’t ever do twice what you coulddo only once.1This standardly means writing a procedure whenever you are going to do the samecomputation more than once. In this section, we’ll explore ways of using procedures to capturecommon patterns in ways that might be new to you.What if we find that we’re often wanting to perform the same procedure twice on an argument?That is, we seem to keep writing square(square(x)). If it were always the same procedure wewere applying twice, we could just write a new functiondef squaretwice(x):return square(square(x))But what if it’s different functions? The usual strategies for abstraction seem like they won’t work.In the functional programming style, we treat functions as first-class objects. So, for example, wecan do:>>> m = square>>> m(7)49And so we can write a procedure that consumes a function as an argument. So, now we couldwrite:def doTwice(f, x):return f(f(x))This is cool, because we can apply it to any function and argument. So, if we wanted to squaretwice, we could do:1Okay, so the main reason behind this rule isn’t laziness. It’s that if you write the same thing more than once, itwill make it harder to write, read, debug, and modify your code reliably.6.01, Spring Semester, 2008—Course notes for Week 2 2>>> doTwice(square,2)16Python gives us a way to define functions without naming them. The expression lambda y: y +y denotes a function of a single variable; in this case it is a function that takes numbers as input,and doubles them. In Python, lambda doesn’t require a return expression, and it can only be usedwith a single expression; you can’t have if or for inside a lambda expression. If you need to putthose in a function, you have to name that function explicitly.Another way to apply a procedure multiple times is this:def doTwiceMaker(f):return lambda x: f(f(x))This is a procedure that returns a procedure! If you’d rather not use lambda, you could write itthis way:def doTwiceMaker(f):def twoF(x):return f(f(x))return twoFNow, to use doTwiceMaker, we could do:>>> twoSquare = doTwiceMaker(square)>>> twoSquare(2)16>>> doTwiceMaker(square)(2)16A somewhat deeper example of capturing common patterns is sums. Mathematicians have inventeda notation for writing sums of series, such as100Xi=1i or100Xi=1i2.Here’s one that gives us a way to compute π:π2/8 =Xi=1,3,5,...1i2.It would be easy enough to write a procedure to compute any one of them. But even better is towrite a higher-order procedure that allows us to compute any of them, simply:def summation(low, high, f, next):s = 0x = lowwhile x <= high:s = s + f(x)x = next(x)return s6.01, Spring Semester, 2008—Course notes for Week 2 3This procedure takes integers specifying the lower and upper bounds of the index of the sum, thefunction of the index that is supposed to be added up, and a function that computes the nextvalue of the index from the previous one. This last feature actually makes this notation moreexpressive than the usual mathematical notation, because you can specify any function you’d likefor incrementing the index. Now, given that definition for sum, we can do all the special cases wedescribed in mathematical notatation above:def sumint(low,high):return summation(low, high, lambda x: x, lambda x: x+1)def sumsquares(low,high):return summation(low, high, lambda x: x**2, lambda x: x+1)def piSum(low,high):return summation(low, high, lambda x: 1.0/x**2, lambda x: x+2)>>> (8 * piSum(1, 1000000))**0.53.1415920169700393Now, we can use this to build an even cooler higher-order procedure. You’ve seen the idea ofapproximating an integral using a sum. We can express it easily in Python, using our sum higher-order function, asdef integral(f, a, b):dx = 0.0001return dx * summation(a, b, f, lambda(x): x + dx)>>> integral(lambda x: x**3, 0, 1)0.2500500024999337We’ll do one more example of a very powerful higher-order procedure. In the previous chapter, wesaw an iterative procedure for computing square roots. We can see that procedure as a special caseof a more general process of computing the fixed-point of a function. The fixed point of a functionf, called f∗, is defined as the value such that f∗= f(f∗). Fixed points can be computed by startingat an initial value v0, and iteratively applying f: f∗= f(f(f(f(f(. . . f(v0)))))). A function may havemany fixed points, and which one you’ll get may depend on the v0you start with.We can capture this idea in Python with:def closeEnough(g1,g2):return abs(g1-g2)<.0001def fixedPoint(f,guess):next=f(guess)while not closeEnough(guess, next):guess=nextnext=f(next)return nextAnd now, we can use this to write the square root procedure much more compactly:6.01, Spring Semester, 2008—Course notes for Week 2 4def sqrt(x):return fixedPoint(lambda g: average(g,x/g), 1.0)Another way to think of square roots is that to compute the square root of x, we need to find they that solves the equationx = y2,or, equivalently,y2− x = 0 .We can try to solve this equation using Newton’s method for finding roots, which is another instanceof a fixed-point computation.2In order to find a solution to the equation f(x) = 0, we can find afixed point of a different function, g, whereg(x) = x −f(x)Df(x).The first step toward turning this into Python code is to write a procedure for computing derivatives.We’ll do it by approximation here, though there are algorithms that can compute the derivative of afunction analytically, for some kinds of functions (that is, they know things like that the derivativeof x3is 3x2.)dx = 1.e-4def deriv(f):return lambda x:(f(x+dx)-f(x))/dx>>> deriv(square)<function <lambda> at
View Full Document
Unlocking...