6 01 Spring Semester 2008 Course notes for Week 2 1 MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6 01 Introduction to EECS I Spring Semester 2008 Course notes for Week 2 1 Higher order functions Another element of functional programming style is the idea of functions as first class objects That means that we can treat functions or procedures in much the same way we treat numbers or strings in our programs we can pass them as arguments to other procedures and return them as the results from procedures This will let us capture important common patterns of abstraction and will also be an important element of object oriented programming We ve been talking about the fundamental principles of software engineering as being modularity and abstraction But another important principle is laziness Don t ever do twice what you could do only once 1 This standardly means writing a procedure whenever you are going to do the same computation more than once In this section we ll explore ways of using procedures to capture common 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 we were applying twice we could just write a new function def 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 we can do m square m 7 49 And so we can write a procedure that consumes a function as an argument So now we could write 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 square twice we could do 1 Okay so the main reason behind this rule isn t laziness It s that if you write the same thing more than once it will 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 16 Python 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 used with a single expression you can t have if or for inside a lambda expression If you need to put those 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 it this way def doTwiceMaker f def twoF x return f f x return twoF Now to use doTwiceMaker we could do twoSquare doTwiceMaker square twoSquare 2 16 doTwiceMaker square 2 16 A somewhat deeper example of capturing common patterns is sums Mathematicians have invented a notation for writing sums of series such as 100 X i 100 X or i 1 i2 i 1 Here s one that gives us a way to compute 2 8 X i 1 3 5 1 i2 It would be easy enough to write a procedure to compute any one of them But even better is to write a higher order procedure that allows us to compute any of them simply def summation low high f next s 0 x low while x high s s f x x next x return s 6 01 Spring Semester 2008 Course notes for Week 2 3 This procedure takes integers specifying the lower and upper bounds of the index of the sum the function of the index that is supposed to be added up and a function that computes the next value of the index from the previous one This last feature actually makes this notation more expressive than the usual mathematical notation because you can specify any function you d like for incrementing the index Now given that definition for sum we can do all the special cases we described 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 5 3 1415920169700393 Now we can use this to build an even cooler higher order procedure You ve seen the idea of approximating an integral using a sum We can express it easily in Python using our sum higherorder function as def integral f a b dx 0 0001 return dx summation a b f lambda x x dx integral lambda x x 3 0 1 0 2500500024999337 We ll do one more example of a very powerful higher order procedure In the previous chapter we saw an iterative procedure for computing square roots We can see that procedure as a special case of a more general process of computing the fixed point of a function The fixed point of a function f called f is defined as the value such that f f f Fixed points can be computed by starting at an initial value v0 and iteratively applying f f f f f f f f v0 A function may have many fixed points and which one you ll get may depend on the v0 you start with We can capture this idea in Python with def closeEnough g1 g2 return abs g1 g2 0001 def fixedPoint f guess next f guess while not closeEnough guess next guess next next f next return next And now we can use this to write the square root procedure much more compactly 6 01 Spring Semester 2008 Course notes for Week 2 4 def 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 the y that solves the equation x y2 or equivalently y2 x 0 We can try to solve this equation using Newton s method for finding roots which is another instance of a fixed point computation 2 In order to find a solution to the equation f x 0 we can find a fixed point of a different function g where g 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 a function analytically for some kinds of functions that is they know things like that the derivative of x3 is 3x2 …
View Full Document
Unlocking...