howto-functional.pdf

Functional Programming HOWTO

Release2.7.6

Guido van Rossum

Fred L. Drake, Jr., editor

March 17, 2014

PythonSoftwareFoundation

Email:docs@python.org

Contents

1Introduction

1.1

Formal provability

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

1.2

Modularity

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

1.3

Ease of debugging and testing

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

1.4

Composability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

2Iterators

2.1

Data Types That Support Iterators

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3Generatorexpressionsandlistcomprehensions

4Generators

vii

4.1

Passing values into a generator

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

5Built-infunctions

6Smallfunctionsandthelambdaexpression

xii

7Theitertoolsmodule

xiii

7.1

Creating new iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xiii

7.2

Calling functions on elements

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xiv

7.3

Selecting elements

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.4

Grouping elements

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8Thefunctoolsmodule

xvi

8.1

The operator module

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xvi

9RevisionHistoryandAcknowledgements

xvii

10References xvii

10.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii

10.2 Python-speciﬁc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii

10.3 Python documentation

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii

Index xix

AuthorA. M. Kuchling

Release0.31

In this document, we’ll take a tour of Python’s features suitable for implementing programs in a functional style.

After an introduction to the concepts of functional programming, we’ll look at language features such asiterators

andgenerators and relevant library modules such as itertools and functools .

1 Introduction

This section explains the basic concept of functional programming; if you’re just interested in learning about

Python language features, skip to the next section.

Programming languages support decomposing problems in several different ways:

• Most programming languages areprocedural: programs are lists of instructions that tell the computer what

to do with the program’s input. C, Pascal, and even Unix shells are procedural languages.

• Indeclarativelanguages, you write a speciﬁcation that describes the problem to be solved, and the language

implementation ﬁgures out how to perform the computation efﬁciently. SQL is the declarative language

you’re most likely to be familiar with; a SQL query describes the data set you want to retrieve, and the SQL

engine decides whether to scan tables or use indexes, which subclauses should be performed ﬁrst, etc.

•Object-orientedprograms manipulate collections of objects. Objects have internal state and support meth-

ods that query or modify this internal state in some way. Smalltalk and Java are object-oriented languages.

C++ and Python are languages that support object-oriented programming, but don’t force the use of object-

oriented features.

•Functionalprogramming decomposes a problem into a set of functions. Ideally, functions only take inputs

and produce outputs, and don’t have any internal state that affects the output produced for a given input.

Well-known functional languages include the ML family (Standard ML, OCaml, and other variants) and

Haskell.

The designers of some computer languages choose to emphasize one particular approach to programming. This

often makes it difﬁcult to write programs that use a different approach. Other languages are multi-paradigm

languages that support several different approaches. Lisp, C++, and Python are multi-paradigm; you can write

programs or libraries that are largely procedural, object-oriented, or functional in all of these languages. In a large

program, different sections might be written using different approaches; the GUI might be object-oriented while

the processing logic is procedural or functional, for example.

In a functional program, input ﬂows 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 aren’t visible in the function’s return value. Functions that have no side effects at all are called

purelyfunctional. 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.

Some languages are very strict about purity and don’t even have assignment statements such as a=3 or c=a

+b , but it’s difﬁcult to avoid all side effects. Printing to the screen or writing to a disk ﬁle are side effects, for

example. For example, in Python a print statement or a time.sleep(1) both return no useful value; they’re

only called for their side effects of sending some text to the screen or pausing execution for a second.

Python programs written in functional style usually won’t go to the extreme of avoiding all I/O or all assignments;

instead, they’ll provide a functional-appearing interface but will use non-functional features internally. For ex-

ample, the implementation of a function will still use assignments to local variables, but won’t modify global

variables or have other side effects.

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

sules 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 ﬂowing between functions. In Python you might combine the two

approaches by writing functions that take and return instances representing objects in your application (e-mail

messages, transactions, etc.).

Functional design may seem like an odd constraint to work under. Why should you avoid objects and side effects?

There are theoretical and practical advantages to the functional style:

• Formal provability.

• Modularity.

• Composability.

• Ease of debugging and testing.

1.1 Formal provability

A theoretical beneﬁt is that it’s easier to construct a mathematical proof that a functional program is correct.

For a long time researchers have been interested in ﬁnding ways to mathematically prove programs correct. This is

different from testing a program on numerous inputs and concluding that its output is usually correct, or reading a

program’s source code and concluding that the code looks right; the goal is instead a rigorous proof that a program

produces the right result for all possible inputs.

The technique used to prove programs correct is to write downinvariants, properties of the input data and of

the program’s variables that are always true. For each line of code, you then show that if invariants X and Y are

truebeforethe line is executed, the slightly different invariants X’ and Y’ are trueafterthe line is executed. This

continues until you reach the end of the program, at which point the invariants should match the desired conditions

on the program’s output.

Functional programming’s avoidance of assignments arose because assignments are difﬁcult to handle with this

technique; assignments can break invariants that were true before the assignment without producing any new

invariants that can be propagated onward.

Unfortunately, proving programs correct is largely impractical and not relevant to Python software. Even trivial

programs require proofs that are several pages long; the proof of correctness for a moderately complicated program

would be enormous, and few or none of the programs you use daily (the Python interpreter, your XML parser,

your web browser) could be proven correct. Even if you wrote down or generated a proof, there would then be the

question of verifying the proof; maybe there’s an error in it, and you wrongly believe you’ve proved the program

correct.

1.2 Modularity

A more practical beneﬁt of functional programming is that it forces you to break apart your problem into small

pieces. Programs are more modular as a result. It’s easier to specify and write a small function that does one thing

than a large function that performs a complicated transformation. Small functions are also easier to read and to

check for errors.

1.3 Ease of debugging and testing

Testing and debugging a functional-style program is easier.

Debugging is simpliﬁed because functions are generally small and clearly speciﬁed. When a program doesn’t

work, each function is an interface point where you can check that the data are correct.

You can look at the

intermediate inputs and outputs to quickly isolate the function that’s responsible for a bug.

Testing is easier because each function is a potential subject for a unit test. Functions don’t depend on system

state that needs to be replicated before running a test; instead you only have to synthesize the right input and then

check that the output matches expectations.

1.4 Composability

As you work on a functional-style program, you’ll write a number of functions with varying inputs and outputs.

Some of these functions will be unavoidably specialized to a particular application, but others will be useful in a

wide variety of programs. For example, a function that takes a directory path and returns all the XML ﬁles in the

directory, or a function that takes a ﬁlename and returns its contents, can be applied to many different situations.

Over time you’ll form a personal library of utilities. Often you’ll assemble new programs by arranging existing

functions in a new conﬁguration and writing a few functions specialized for the current task.

2 Iterators

I’ll start by looking at a Python language feature that’s an important foundation for writing functional-style pro-

grams: iterators.

An iterator is an object representing a stream of data; this object returns the data one element at a time. A Python

iterator must support a method called next() that takes no arguments and always returns the next element of

the stream. If there are no more elements in the stream, next() must raise the StopIteration exception.

Iterators don’t have to be ﬁnite, though; it’s perfectly reasonable to write an iterator that produces an inﬁnite

stream of data.

The built-in iter() function takes an arbitrary object and tries to return an iterator that will return the object’s

contents or elements, raising TypeError if the object doesn’t support iteration. Several of Python’s built-in data

types support iteration, the most common being lists and dictionaries. An object is called aniterableobject if you

can get an iterator for it.

You can experiment with the iteration interface manually:

>>> L = [ 1 , 2 , 3 ]

>>> it = iter (L)

>>> print it

<...iteratorobjectat...>

>>> it . next()

Traceback(mostrecentcalllast):

File "<stdin>" ,line 1 ,in?

StopIteration

>>>

Python expects iterable objects in several different contexts, the most important being the for statement. In the

statement forXinY , Y must be an iterator or some object for which iter() can create an iterator. These

two statements are equivalent:

for i in iter (obj):

print i

for i in obj:

print i

Iterators can be materialized as lists or tuples by using the list() or tuple() constructor functions:

>>> L = [ 1 , 2 , 3 ]

>>> iterator = iter (L)

>>> t = tuple (iterator)

>>> t

(1,2,3)

Sequence unpacking also supports iterators: if you know an iterator will return N elements, you can unpack them

into an N-tuple:

>>> L = [ 1 , 2 , 3 ]

>>> iterator = iter (L)

>>> a,b,c = iterator

>>> a,b,c

(1,2,3)

Built-in functions such as max() and min() can take a single iterator argument and will return the largest or

smallest element. The "in" and "notin" operators also support iterators: Xiniterator is true if X is

found in the stream returned by the iterator. You’ll run into obvious problems if the iterator is inﬁnite; max() ,

min() will never return, and if the element X never appears in the stream, the "in" and "notin" operators

won’t return either.

Note that you can only go forward in an iterator; there’s no way to get the previous element, reset the iterator, or

make a copy of it. Iterator objects can optionally provide these additional capabilities, but the iterator protocol

only speciﬁes the next() method. Functions may therefore consume all of the iterator’s output, and if you need

to do something different with the same stream, you’ll have to create a new iterator.

2.1 Data Types That Support Iterators

We’ve already seen how lists and tuples support iterators. In fact, any Python sequence type, such as strings, will

automatically support creation of an iterator.

Calling iter() on a dictionary returns an iterator that will loop over the dictionary’s keys:

>>> m = { ’Jan’ : 1 , ’Feb’ : 2 , ’Mar’ : 3 , ’Apr’ : 4 , ’May’ : 5 , ’Jun’ : 6 ,

... ’Jul’ : 7 , ’Aug’ : 8 , ’Sep’ : 9 , ’Oct’ : 10 , ’Nov’ : 11 , ’Dec’ : 12 }

>>> for key in m:

... print key,m[key]

Mar3

Feb2

Aug8

Sep9

Apr4

Jun6

Jul7

Jan1

May5

Nov11

Dec12

Oct10

Note that the order is essentially random, because it’s based on the hash ordering of the objects in the dictionary.

Applying iter() to a dictionary always loops over the keys, but dictionaries have methods that return other

iterators. If you want to iterate over keys, values, or key/value pairs, you can explicitly call the iterkeys() ,

itervalues() , or iteritems() methods to get an appropriate iterator.

The dict() constructor can accept an iterator that returns a ﬁnite stream of (key,value) tuples:

>>> L = [( ’Italy’ , ’Rome’ ),( ’France’ , ’Paris’ ),( ’US’ , ’WashingtonDC’ )]

>>> dict ( iter (L))

{’Italy’:’Rome’,’US’:’WashingtonDC’,’France’:’Paris’}

Files also support iteration by calling the readline() method until there are no more lines in the ﬁle. This

means you can read each line of a ﬁle like this:

for line in file :

#dosomethingforeachline

...

Sets can take their contents from an iterable and let you iterate over the set’s elements:

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: