CS计算机代考程序代写 python data structure compiler 1

1

CMPSC-132: Programming and Computation II

Department of Computer Science & Engineering
The Pennsylvania State University

1. Functional Programming
Functional programming decomposes a problem into a set of functions. In a functional program, input

flows through a set of functions. Each function operates on its input and produces some output. Functional

style discourages functions with side effects that modify internal state or make other changes that are not

visible in the function’s return value. Functions that have no side effects at all are called purely functional.

Avoiding side effects means not using data structures that get updated as a program runs; every function’s

output must only depend on its input. However, it is difficult to avoid all side effects. Printing to the screen

or writing to a disk file are examples of side effects.

Functional programming can be considered the opposite of object-oriented programming. Objects are

little capsules containing some internal state along with a collection of method calls that let you modify

this state, and programs consist of making the right set of state changes. Functional programming wants to

avoid state changes as much as possible and works with data flowing between functions. In Python you

might combine the two approaches by writing functions that take and return instances representing objects

in your application. Functional design may seem like an odd constraint to work under but it has theoretical

and practical advantages for formal provability, molarity, composability and ease of debugging and testing.

1.1 Higher-Order functions

We have seen that functions are a method of abstraction that describe compound operations

independent of the particular values of their arguments. For example:

def square(x):

return x * x

in the square function from above, we are not talking about the square of a particular number, but rather

about a method for obtaining the square of any number. Of course, we could get along without ever defining

this function, by always writing expressions such as 3 * 3, 9 * 9, 12 * 12, etc. This practice would suffice

for simple computations such as square, but would become arduous for more complex examples such as fib

(Fibonacci series). In general, lacking function definition would put us at the disadvantage of forcing us to

work always at the level of the particular operations that happen to be primitives in the language

(multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able

to compute squares, but our language would lack the ability to express the concept of squaring.

One of the things we should demand from a programming language is the ability to build abstractions

by assigning names to common patterns and then to work in terms of the names directly. Functions provide

this ability. To express certain general patterns as named concepts, we will need to construct functions that

2

can accept other functions as arguments or return functions as values. Functions that manipulate functions

are called higher-order functions.

1.1.1 Functions as arguments

Consider the following two functions, which all compute summations. The first, sum_naturals,

computes the sum of natural numbers up to n:

def sum_naturals(n):

total, k = 0, 1

while k <= n: total, k = total + k, k + 1 return total sum_naturals(100) #5050 The second, sum_cubes, computes the sum of the cubes of natural numbers up to n: def sum_cubes(n): total, k = 0, 1 while k <= n: total, k = total + k*k*k, k + 1 return total sum_cubes(100) #25502500 These two functions clearly share a common underlying pattern. They are for the most part identical, differing only in name and the function of k used to compute the term to be added. We could generate each of the functions by filling in slots in the same template: def (n):
total, k = 0, 1

while k <= n: total, k = total + (k), k + 1

return total

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be

brought to the surface. Each of these functions is a summation of terms. When designing your programs,

you would like your language to be powerful enough so that you can write a function that expresses the

concept of summation itself rather than only functions that compute particular sums. We can do so readily

in Python by taking the common template shown above and transforming the “slots” into formal

parameters. In the example below, summation() takes as its two arguments the upper bound n together with

the function term that computes the k-th term. We can use summation just as we would any function, and

it expresses summations succinctly. Take the time to step through this example, and notice how binding

cube to the local name term ensures that the result 1*1*1 + 2*2*2 + 3*3*3 = 36 is computed correctly:

def summation(n, term):

total, k = 0, 1

while k <= n: total, k = total + term(k), k + 1 return total def cube(x): return x*x*x def sum_cubes(n): return summation(n, cube) result = sum_cubes(3) print(result) 3 1.1.2 Functions as returned values We can achieve even more expressive power in our programs by creating functions whose returned values are themselves functions. An important feature of lexically scoped programming languages is that locally defined functions maintain their parent environment when they are returned. Once many simple functions are defined, function composition is a natural method of combination to include in our programming language. That is, given two functions f(x) and g(x), we might want to define h(x) = f(g(x)). We can define function composition using our existing tools: def compose_f(f, g): def h(x): return f(g(x)) return h The following example illustrates the utility of this feature: def square(x): return x * x def successor(x): return x + 1 def fun_compose(f, g): def h(x): return f(g(x)) return h square_successor = fun_compose(square, successor) result = square_successor(10) print(result) #121 Both square and successor functions take one argument, thus, the fun_composed functions all take a single argument as well. 1.2 Lambda Expressions So far, each time we have wanted to define a new function, we needed to give it a name. The lambda expression is a way to create small anonymous functions (functions without a name). These functions are throw-away functions (just needed where they have been created). Lambda functions are mainly used in combination with the functions filter(), map() and reduce(). The following example of a lambda function returns the sum of its two arguments: sum = lambda x, y : x + y sum(3,4) >>> 7

In general, Python style prefers explicit def statements to lambda expressions, but allows them in cases

where a simple function is needed as an argument or return value. Such stylistic rules are merely guidelines;

you can program any way you wish. However, as you write programs, think about the audience of people

who might read your program one day and think if your program is easy to understand.

def sum(x,y):

return x + y

sum(3,4)

>>> 7

4

1.2.1 The map() function

map() takes a function and a collection of items. It makes a new, empty collection, runs the function on

each item in the original collection and inserts each return value into the new collection. It returns the new

collection.
r = map(function_to_apply, list_of_inputs)

The code below is a simple map that takes a list of names and returns a list of the lengths of those

names:

name_lengths = map(len, [“Alex”, “Sandy”, “Jeffrey”])

print(list(name_lengths))

# >>> [4, 5, 7]

The advantage of the lambda operator can be seen when it is used in combination with the map()

function:

squares = map(lambda x: x * x, [0, 1, 2, 3, 4, 5])

print(list(squares))

# >>> [0, 1, 4, 9, 16, 25]

This is a map that squares every number in the passed collection and does not take a named function. It

takes an anonymous, inlined function defined with lambda. The parameters of the lambda are defined to

the left of the colon. The function body is defined to the right of the colon. The result of running the function

body is implicitly returned. map() can be applied to more than one list, however, the lists must have the

same length.

1.2.2 The filter() function

filter() offers an elegant way to filter out all the elements of a sequence for which a function returns

True:

r = filter(function_to_apply, list_of_inputs)

The function filter(function_to_apply, list_of_inputs) needs a function as its first argument. This function

has to return a Boolean value and will be applied to every element of the list. The example below outputs

First, turn the map into a list…

Before Python 3, map() used to return a list, where each element of the result list was the result of

the function applied on the corresponding element of the list or tuple. With Python 3, map() returns an

iterator.

5

all the negative values in a sequence of numbers (In this example, the filter resembles a for loop but it is a

faster built-in function):

number_list = range(-5, 5)

less_than_zero = filter(lambda x: x < 0, number_list) print(list(less_than_zero)) # Output: [-5, -4, -3, -2, -1] 1.2.3 The reduce() function reduce() is a really useful function for performing some computation on a list and returning the result. While map will apply a function over a sequence, producing a sequence as output, reduce will apply a function of two arguments cumulatively to the items in a sequence, in order to reduce the sequence to a single value. In Python 3, reduce() is not a core built-in function anymore and it has been moved to functools (still part of the standard library), thus, in order to use it you need to import it like this: from functools import reduce. To illustrate how reduce works, lets use as an example the product of a list of integers. The common way this task can be programmed in python is using a basic for loop: product = 1 list = [1, 2, 3, 4, 5] for num in list: product = product * num print(product) # Output: 120 Using reduce, the code above can be written like this: from functools import reduce product = reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) print(product) # Output: 120 The function reduce((lambda x, y: x * y), [1, 2, 3, 4, 5]) continually applies the lambda function to the sequence [1, 2, 3, 4, 5] returning a single value. 1 2 3 4 5 2 6 24 120 6 At first the first two elements of the sequence will be applied to the function. In the next step the function will be applied on the previous result and the third element of the list, continuing like this until just one element is left and returning this element as the result of reduce(). 1.3 Operators There are many built-in functions in Python that accept functions as arguments. An example is the filter() function that was used previously. However, there are some basic actions that use operators instead of functions (like +, [], or . operators). The operator module provides function versions of these operators. import operator operator.add(1, 6) # Output: 7 It is possible to create functions dynamically that can know which item to get from a list: import operator get_second = operator.itemgetter(1) get_second(['a', 'b', 'c', 'd']) # Output: 'b' The itemgetter() function will return a tuple if it is given more than one index. import operator get_two = operator.itemgetter(0, 2) get_two(['a', 'b', 'c', 'd']) # Output: ('a', 'c') A typical use for the itemgetter() function is as the key argument to a list sort. import operator band = [('Guitar', 'Jimmy'), ('Vocals', 'Robert'), ('Bass', 'John'), ('Drums', 'John')] sorted(band) [('Bass', 'John Paul'), ('Drums', 'John'), ('Guitar', 'Jimmy'), ('Vocals', 'Robert')] sorted(band, key=operator.itemgetter(1)) [('Guitar', 'Jimmy'), ('Drums', 'John'), ('Bass', 'John'), ('Vocals', 'Robert')] For more operators, read https://docs.python.org/3/library/operator.html 1.4 Function Decorators A function decorator is applied to a function definition by placing it on the line before that function definition begins: @myDecorator def aFunction(): print("inside aFunction") https://docs.python.org/3/library/operator.html 7 When the compiler passes over this code, aFunction() is compiled and the resulting function object is passed to the myDecorator code, which does something to produce a function-like object that is then substituted for the original aFunction(). Function decorators are simply wrappers to existing functions. Putting the ideas mentioned above together, we can build a decorator. In this example lets consider a function that wraps the string output of another function in

tags.

def get_text(name):

return “Dear {0}, Thank you for your note…”.format(name)

def p_decorate(func):

def func_wrapper(name):

return “

{0}

“.format(func(name))

return func_wrapper

my_get_text = p_decorate(get_text)

print(my_get_text(“John”))

# Output:

Dear John, Thank you for your note…

A function that takes another function as an argument, generates a new function, augmenting the work of

the original function, and returning the generated function so we can use it anywhere. To have get_text

itself be decorated by p_decorate, we just have to assign get_text to the result of p_decorate:

def get_text(name):

return “Dear {0}, Thank you for your note…”.format(name)

def p_decorate(func):

def func_wrapper(name):

return “

{0}

“.format(func(name))

return func_wrapper

get_text = p_decorate(get_text)

print(get_text(“John”))

# Output:

Dear John, Thank you for your note…

Another thing to notice is that our decorated function takes a name argument. All what we had to do in the

decorator is to let the wrapper of get_text pass that argument. Because this is such a common programming

idiom in Python, there is a special decorator syntax to simplify its use which is to mention the name of the

decorating function before the function to be decorated. The name of the decorator should be perpended

with an @ symbol:
def p_decorate(func):

def func_wrapper(name):

return “

{0}

“.format(func(name))

return func_wrapper

@p_decorate

def get_text(name):

return “Dear {0}, Thank you for your note…”.format(name)

print(get_text(“John”))

# Output:

Dear John, Thank you for your note…

8

In other words, this Python syntax:

@some_decorator

def some_function():

# statements

is equivalent to:

def some_function():

# statements

some_function = some_decorator(some_function)

Now, imagine you want to decorate the get_text function by 2 other functions to wrap a