関数型プログラミング HOWTO
**************************

Author:
   A. M. Kuchling

Release:
   0.31

この文書では、関数型スタイルでプログラムを実装するのにピッタリな
Python の機能を見てまわることにしましょう。まず関数型プログラミングと
いう概念を紹介したあと、 *iterator* や *generator* のような言語機能、
および "itertools" や "functools" といった関連するライブラリモジュール
を見ることにします。


はじめに
========

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.

プログラミング言語とは問題を分解するものですが、各言語がサポートする分
解方法にはいくつかの種類があります:

* ほとんどのプログラミング言語は **手続き型** です: プログラムは、入
  力 に対して行うべきことをコンピュータに教える指示リストとなります。
  C, Pascal, さらには Unix シェルまでもが手続き型言語に入ります。

* **宣言型** 言語で書くのは、解くべき問題を説明する仕様書であって、
  そ れを効率的に計算処理する方法を見付けるのは言語実装の役目です。SQL
  は おそらく一番よく知られた宣言型言語です; SQL のクエリは取得したい
  デー タセットを説明しているだけで、テーブルを走査するかインデックス
  を使う か、どのサブクローズから実行するか等々を決めるのは SQL エンジ
  ンなの です。

* **オブジェクト指向** プログラムはオブジェクトの集まりを操作します
  。 オブジェクトには内部状態があり、その状態を調べたり色々と変更した
  りす るためのメソッドがあります。Smalltalk や Java はオブジェクト指
  向言語 です。 C++ と Python はオブジェクト指向プログラミングをサポー
  トして いますが、関連する機能を使わなくても構わないようになっていま
  す。

* **関数型** プログラミングは問題をいくつかの関数にわけて考えます。
  理 想的に言うと、関数は入力を受けて出力を吐くだけで、同じ入力に対し
  て異 なる出力をするような内部状態を一切持ちません。有名な関数型言語
  には ML 一家 (Standard ML, OCaml 等々) と Haskell があります。

The designers of some computer languages choose to emphasize one
particular approach to programming.  This often makes it difficult 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.

関数型プログラムでは、入力は一連の関数を通って流れていきます。それぞれ
の関数は入力に何らかの作業をして出力します。関数型スタイルにおいては、
内部状態を変えてしまったり、返り値に現れない変更をしたりといった副作用
のある関数はやめるように言われています。副作用のまったくない関数は **
純粋関数型** であるとされます。副作用をなくすということは、プログラム
の実行中に順次変化していくデータ構造を持たない、つまり各関数の出力はそ
の入力にしか影響を受けてはいけないということです。

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 difficult
to avoid all side effects.  Printing to the screen or writing to a
disk file 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 プログラムはふつう、I/O や代入を完全にな
くすといった極端なところまでは行かずに、関数型っぽく見えるインタフェー
スを提供しつつも内部では非関数型の機能を使います。たとえば、関数内でロ
ーカル変数の代入は使いますが、グローバル変数は変更せず、他の副作用もな
いように実装するのです。

関数型プログラミングはオブジェクト指向プログラミングの反対と考えること
もできます。オブジェクト指向において、オブジェクトは内部状態とそれを変
更するメソッドコールの入ったカプセルであり、プログラムはその状態を適正
に変化させていく手順です。一方で、関数型プログラミングは可能なかぎり状
態の変更を避け、関数どうしの間を流れるデータだけを扱おうとします。
Python ではこの二つのアプローチを結び合わせることができます。アプリケ
ーション内のオブジェクト (メール、トランザクション、等々) を表現したイ
ンスタンスを、関数が受け渡しするようにするのです。

関数型デザインは、わけのわからない制約に見えるかもしれません。どうして
オブジェクトも副作用もないほうが良いのでしょうか。実は、関数型スタイル
には理論と実践に基づく次の利点があるのです:

* 形式的証明可能性。

* モジュラー性。

* 結合性。

* デバッグやテストの簡単さ。


形式的証明可能性
----------------

理論面の利点としては、プログラムが正しいことの数学的証明を他より簡単に
構築できるという点があります。

研究者たちは長いあいだ、プログラムが正しいことを数学的に証明する方法の
発見に血道をあげてきました。これは、色々な入力でテストして出力が正しか
ったからまあ正しいだろう、と結論するのとも違いますし、ソースコードを読
んで「間違いはなさそうだ」と言うのとも別の話です; 目指すのは、出現しう
る入力すべてに対してプログラムが正しい結果を出すことの厳密な証明なので
す。

プログラムを証明するために使われているのは **不変式** を書き出していく
というテクニックで、不変式とは入力データやプログラム変数のうち常に真で
ある性質のことです。コードの一行一行で、 **実行前** の不変式 X と Y が
真なら **実行後に** ちょっと違う不変式 X』 と Y』 が真になることを示し
ていき、これをプログラムの終わりまで続けるわけです。すると最終的な不変
式はプログラムの出力に合った条件になっているはずです。

関数型プログラミングが代入を嫌うのは、この不変式テクニックでは代入を扱
いにくいからです; 代入は、それまで真だった不変式を壊しておいて、自分は
次の行に伝えてゆける不変式を生み出さないことがあるのです。

残念ながら、プログラムの証明はだいたい実際的でもありませんし、Python
ソフトウェアにも関係ありません。本当に簡単なプログラムでも、証明には数
ページにわたる論文が必要なのです; ある程度の複雑なプログラムではもう尋
常でない長さになってしまうので、日常で使っているプログラム (Python イ
ンタプリタ、XML パーサ、ウェブブラウザ) はほとんど、あるいはすべて、正
しさを証明するのは不可能でしょう。仮に証明を書き出したり生成したりして
も、その証明を検証するための疑いが残ります; 証明に間違いがあるかもしれ
ず、その場合は証明したと自分で勝手に思い込んでいただけになるのです。


モジュラー性
------------

より実用的には、関数型プログラミングをすると問題を細かく切り分けること
になるという利点があります。結果としてプログラムはモジュラー化されます
。複雑な変形を施す大きな関数を書くより、一つのことに絞ってそれだけをす
る小さな関数のほうが書きやすいものです。それに、小さいほうが読むのもエ
ラーをチェックするのも簡単です。


デバグやテストの簡単さ
----------------------

テストやデバグも関数型プログラムなら簡単です。

関数が一般的に小さくて明確に意味付けされているので、デバグ方法は単純で
す。プログラムが正しく動かないときには、関数ひとつひとつがデータの正し
さをチェックするポイントになるので、それぞれの時点における入力と出力を
見ていけば、バグの原因となる関数を素早く切り出すことができるのです。

ひとつひとつの関数がユニットテストの対象になり得るわけですから、テスト
も簡単です。関数はシステムの状態に依存しませんので、テストの実行前にそ
うした状態を再現する必要はありません; 単に適切な入力を合成して、出力が
期待どおりかどうかチェックするだけで良いのです。


結合性
------

関数型スタイルのプログラムを作っていると、色々な入力や出力のために色々
な関数を書くことになります。仕方なく特定のアプリケーションに特化した関
数を書くこともあるでしょうけれど、広範なプログラムに使える関数もあるこ
とでしょう。たとえば、ディレクトリ名を受け取ってその中の XML ファイル
一覧を返す関数や、ファイル名を受け取って内容を返す関数などは、多様な場
面に適用できそうです。

時たつうちに自分の特製ライブラリやユーティリティが充実してくると、新し
いプログラムも、既存の関数を調整して少し今回に特化した関数を書くだけで
組み立てられるようになります。


イテレータ (iterator)
=====================

まずは関数型スタイルのプログラムを書く際の基礎となる重要な Python 機能
から見ていきましょう: イテレータです。

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 finite, though; it’s perfectly reasonable
to write an iterator that produces an infinite 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 an **iterable**
object if you can get an iterator for it.

手を動かしてイテレータ化の実験をしてみましょう:

>>> L = [1,2,3]
>>> it = iter(L)
>>> print it
<...iterator object at ...>
>>> it.next()
1
>>> it.next()
2
>>> it.next()
3
>>> it.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

Python expects iterable objects in several different contexts, the
most important being the "for" statement.  In the statement "for X in
Y", 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

イテレータは "list()" や "tuple()" といったコンストラクタ関数を使って
リストやタプルに具現化することができます:

>>> L = [1,2,3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)

シーケンスのアンパックもイテレータに対応しています: イテレータが N 個
の要素を返すということが事前にわかっていれば、N-タプルにアンパックする
ことができます:

>>> 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 ""not in"" operators also support iterators: "X in
iterator" is true if X is found in the stream returned by the
iterator.  You’ll run into obvious problems if the iterator is
infinite; "max()", "min()" will never return, and if the element X
never appears in the stream, the ""in"" and ""not in"" 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 specifies 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.


イテレータ対応のデータ型
------------------------

リストやタプルがイテレータに対応している方法については既に見ましたが、
実のところ Python のシーケンス型はどれでも、たとえば文字列なども、自動
でイテレータ生成に対応しています。

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]
   Mar 3
   Feb 2
   Aug 8
   Sep 9
   Apr 4
   Jun 6
   Jul 7
   Jan 1
   May 5
   Nov 11
   Dec 12
   Oct 10

順番は基本的にランダムであることに注目してください。これは辞書内オブジ
ェクトのハッシュの順番になっているからです。

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.

逆に "dict()" コンストラクタは、有限な  "(key, value)" タプルのストリ
ームを返すイテレータを受け入れることができます:

>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
{'Italy': 'Rome', 'US': 'Washington DC', 'France': 'Paris'}

Files also support iteration by calling the "readline()" method until
there are no more lines in the file.  This means you can read each
line of a file like this:

   for line in file:
       # do something for each line
       ...

セットはイテラブルを受け取れますし、そのセットの要素でイテレートするこ
ともできます:

   S = set((2, 3, 5, 7, 11, 13))
   for i in S:
       print i


ジェネレータ式とリスト内包表記
==============================

イテレータの出力に対してよく使う操作トップ 2 は、(1) ひとつずつ全要素
に操作を実行する、および (2) 条件に合う要素でサブセットを作る、です。
たとえば文字列のリストなら、各行のうしろに付いた邪魔なホワイトスペース
を削りたいとか、特定の文字列を含む部分をピックアップしたいなどと思うか
もしれません。

リスト内包表記とジェネレータ式 (略して「listcomp」と「genexp」) は、そ
うした操作向けの簡潔な表記方法です。これは関数型プログラミング言語
Haskell (https://www.haskell.org/) にインスパイアされました。文字列の
ストリームからホワイトスペースをすべて削るのは次のコードでできます:

   line_list = ['  line 1\n', 'line 2  \n', ...]

   # Generator expression -- returns iterator
   stripped_iter = (line.strip() for line in line_list)

   # List comprehension -- returns list
   stripped_list = [line.strip() for line in line_list]

特定の要素だけを選び出すのは ""if"" 条件式を付けることで可能です:

   stripped_list = [line.strip() for line in line_list
                    if line != ""]

リスト内包表記を使うと Python リストが返って来ます; "stripped_list" は
実行結果の行が入ったリストであって、イテレータではありません。ジェネレ
ータ式はイテレータを返し、これだと必要に応じてだけ値を算出しますので、
すべての値を一度に出す必要がありません。つまりリスト内包表記のほうは、
無限長ストリームや膨大なデータを返すようなイテレータを扱う際には、あま
り役に立たないということです。そういった状況ではジェネレータ式のほうが
好ましいと言えます。

ジェネレータ式は丸括弧 「()」 で囲まれ、リスト内包表記は角括弧 「[]」
で囲まれます。ジェネレータ式の形式は次のとおりです:

   ( expression for expr in sequence1
                if condition1
                for expr2 in sequence2
                if condition2
                for expr3 in sequence3 ...
                if condition3
                for exprN in sequenceN
                if conditionN )

リスト内包表記も、外側の括弧が違うだけ (丸ではなく角括弧) で、あとは同
じです。

生成される出力は "expression" 部分の値を要素として並べたものになります
。 "if" 節はすべて、なくても大丈夫です; あれば "condition" が真のとき
だけ "expression" が評価されて出力に追加されます。

ジェネレータ式は常に括弧の中に書かなければなりませんが、関数コールの目
印になっている括弧でも大丈夫です。関数にすぐ渡すイテレータを作りたけれ
ばこう書けるのです:

   obj_total = sum(obj.count for obj in list_all_objects())

"for...in" 節は複数つなげられますが、どれにも、イテレートするためのシ
ーケンスが含まれています。それらのシーケンスは並行して **ではなく** 、
左から右へ順番にイテレートされるので、長さが同じである必要はありません
。 "sequence1" の各要素ごとに毎回最初から "sequence2" をループで回すの
です。その後 "sequence1" と "sequence2" から出た要素ペアごとに、
"sequence3" でループします。

別の書き方をすると、リスト内包表記やジェネレータ式は次の Python コード
と同じ意味になります:

   for expr1 in sequence1:
       if not (condition1):
           continue   # Skip this element
       for expr2 in sequence2:
           if not (condition2):
               continue   # Skip this element
           ...
           for exprN in sequenceN:
               if not (conditionN):
                   continue   # Skip this element

               # Output the value of
               # the expression.

つまり、複数の "for...in" 節があって "if" がないときの最終出力は、長さ
が各シーケンス長の積に等しくなるということです。長さ 3 のリスト二つな
ら、出力リストの長さは 9 要素です:

   >>> seq1 = 'abc'
   >>> seq2 = (1,2,3)
   >>> [(x,y) for x in seq1 for y in seq2]
   [('a', 1), ('a', 2), ('a', 3),
    ('b', 1), ('b', 2), ('b', 3),
    ('c', 1), ('c', 2), ('c', 3)]

Python の文法に曖昧さを紛れ込ませないように、 "expression" でタプルを
作るなら括弧で囲わなくてはなりません。下にあるリスト内包表記で、最初の
は構文エラーですが、二番目は有効です:

   # Syntax error
   [ x,y for x in seq1 for y in seq2]
   # Correct
   [ (x,y) for x in seq1 for y in seq2]


ジェネレータ (generator)
========================

ジェネレータは、イテレータを書く作業を簡単にする、特殊な関数です。標準
的な関数は値を計算して返しますが、ジェネレータが返すのは、一連の値を返
すイテレータです。

Python や C の標準的な関数コールについては、よくご存じに違いありません
。関数を呼ぶと、ローカル変数を作るプライベートな名前空間ができますね。
その関数が "return" 文まで来ると、ローカル変数が破壊されてから、返り値
が呼び出し元に返ります。次に同じ関数をもう一度呼ぶと、新しいプライベー
ト名前空間に新規のローカル変数が作られるのです。しかし、関数を出るとき
にローカル変数を捨てなければどうなるでしょうか。その出ていったところか
ら関数を続行できたとしたら、どうでしょう。これこそジェネレータが提供す
る機能です; すなわち、ジェネレータは続行できる関数と考えることができま
す。

ごく単純なジェネレータ関数の例がこちらにあります:

   def generate_ints(N):
       for i in range(N):
           yield i

Any function containing a "yield" keyword is a generator function;
this is detected by Python’s *bytecode* compiler which compiles the
function specially as a result.

When you call a generator function, it doesn’t return a single value;
instead it returns a generator object that supports the iterator
protocol.  On executing the "yield" expression, the generator outputs
the value of "i", similar to a "return" statement.  The big difference
between "yield" and a "return" statement is that on reaching a "yield"
the generator’s state of execution is suspended and local variables
are preserved.  On the next call to the generator’s ".next()" method,
the function will resume executing.

上記 "generate_ints()" ジェネレータの使用例はこちらです:

>>> gen = generate_ints(3)
>>> gen
<generator object generate_ints at ...>
>>> gen.next()
0
>>> gen.next()
1
>>> gen.next()
2
>>> gen.next()
Traceback (most recent call last):
  File "stdin", line 1, in <module>
  File "stdin", line 2, in generate_ints
StopIteration

同じく "for i in generate_ints(5)" や "a,b,c = generate_ints(3)" とい
った書き方もできます。

Inside a generator function, the "return" statement can only be used
without a value, and signals the end of the procession of values;
after executing a "return" the generator cannot return any further
values.  "return" with a value, such as "return 5", is a syntax error
inside a generator function.  The end of the generator’s results can
also be indicated by raising "StopIteration" manually, or by just
letting the flow of execution fall off the bottom of the function.

You could achieve the effect of generators manually by writing your
own class and storing all the local variables of the generator as
instance variables.  For example, returning a list of integers could
be done by setting "self.count" to 0, and having the "next()" method
increment "self.count" and return it. However, for a moderately
complicated generator, writing a corresponding class can be much
messier.

The test suite included with Python’s library, "test_generators.py",
contains a number of more interesting examples.  Here’s one generator
that implements an in-order traversal of a tree using generators
recursively.

   # A recursive generator that generates Tree leaves in in-order.
   def inorder(t):
       if t:
           for x in inorder(t.left):
               yield x

           yield t.label

           for x in inorder(t.right):
               yield x

ほかにも "test_generators.py" には、N-Queens 問題 (N×N コマのチェス盤
に、互いに攻撃できないような配置で N 個のクイーンを置く) やナイト・ツ
アー (N×N 盤の全コマをナイトが一度ずつ通るような経路を探す) の解を出す
例が入っています。


ジェネレータに値を渡す
----------------------

Python 2.4 までのジェネレータは出力することしかできませんでした。ジェ
ネレータのコードを実行してイテレータを作ってしまったあとで、その関数を
再開するときに新しい情報を渡す手段はなかったのです。ジェネレータがグロ
ーバル変数を見るようにしたり、ミュータブルなオブジェクトを渡しておいて
呼び出し元であとからそれを変更したり、といったハックは可能でしたが、ど
れもゴチャゴチャしていますね。

Python 2.5 で、ジェネレータに値を渡す簡単な手段ができました。 "yield"
が、変数に代入したり演算したりできる値を返す式になったのです:

   val = (yield i)

上のように、返り値で何かをするときは "yield" 式の前後に **必ず** 括弧
を付けるようお勧めします。括弧は常に必要なわけではありませんが、どんな
とき付けなくて良いのかを覚えておくより、いつも付けておくほうが楽ですか
ら。

(PEP 342 explains the exact rules, which are that a "yield"-expression
must always be parenthesized except when it occurs at the top-level
expression on the right-hand side of an assignment.  This means you
can write "val = yield i" but have to use parentheses when there’s an
operation, as in "val = (yield i) + 12".)

Values are sent into a generator by calling its "send(value)" method.
This method resumes the generator’s code and the "yield" expression
returns the specified value.  If the regular "next()" method is
called, the "yield" returns "None".

下にあるのは 1 ずつ増える単純なカウンタですが、内部カウンタの値を変更
することができるようになっています。

   def counter (maximum):
       i = 0
       while i < maximum:
           val = (yield i)
           # If value provided, change counter
           if val is not None:
               i = val
           else:
               i += 1

そしてカウンタ変更の例がこちらです:

>>> it = counter(10)
>>> print it.next()
0
>>> print it.next()
1
>>> print it.send(8)
8
>>> print it.next()
9
>>> print it.next()
Traceback (most recent call last):
  File "t.py", line 15, in <module>
    print it.next()
StopIteration

Because "yield" will often be returning "None", you should always
check for this case.  Don’t just use its value in expressions unless
you’re sure that the "send()" method will be the only method used to
resume your generator function.

In addition to "send()", there are two other new methods on
generators:

* "throw(type, value=None, traceback=None)" is used to raise an
  exception inside the generator; the exception is raised by the
  "yield" expression where the generator’s execution is paused.

* "close()" raises a "GeneratorExit" exception inside the generator
  to terminate the iteration.  On receiving this exception, the
  generator’s code must either raise "GeneratorExit" or
  "StopIteration"; catching the exception and doing anything else is
  illegal and will trigger a "RuntimeError".  "close()" will also be
  called by Python’s garbage collector when the generator is garbage-
  collected.

  "GeneratorExit" が起こったときにクリーンアップ作業をする必要があるな
  ら、 "GeneratorExit" を捕捉するのではなく "try: ... finaly:" するよ
  うお勧めします。

これらの変更の合わせ技で、ジェネレータは情報の一方的な生産者から、生産
者かつ消費者という存在に変貌を遂げたのです。

ジェネレータは **コルーチン** という、より一般化された形式のサブルーチ
ンにもなります。サブルーチンは一カ所 (関数の冒頭) から入って別の一カ所
("return" 文) から出るだけですが、コルーチンはいろいろな場所 ("yield"
文) から入ったり出たり再開したりできるのです。


組み込み関数 (built-in function)
================================

よくイテレータと一緒に使うビルトイン関数について、もっと詳しく見ていき
ましょう。

Two of Python’s built-in functions, "map()" and "filter()", are
somewhat obsolete; they duplicate the features of list comprehensions
but return actual lists instead of iterators.

"map(f, iterA, iterB, ...)" returns a list containing "f(iterA[0],
iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ...".

>>> def upper(s):
...     return s.upper()

>>> map(upper, ['sentence', 'fragment'])
['SENTENCE', 'FRAGMENT']

>>> [upper(s) for s in ['sentence', 'fragment']]
['SENTENCE', 'FRAGMENT']

As shown above, you can achieve the same effect with a list
comprehension.  The "itertools.imap()" function does the same thing
but can handle infinite iterators; it’ll be discussed later, in the
section on the "itertools" module.

"filter(predicate, iter)" returns a list that contains all the
sequence elements that meet a certain condition, and is similarly
duplicated by list comprehensions.  A **predicate** is a function that
returns the truth value of some condition; for use with "filter()",
the predicate must take a single value.

>>> def is_even(x):
...     return (x % 2) == 0

>>> filter(is_even, range(10))
[0, 2, 4, 6, 8]

これはリスト内包表記でも書けます:

>>> [x for x in range(10) if is_even(x)]
[0, 2, 4, 6, 8]

"filter()" also has a counterpart in the "itertools" module,
"itertools.ifilter()", that returns an iterator and can therefore
handle infinite sequences just as "itertools.imap()" can.

"reduce(func, iter, [initial_value])" doesn’t have a counterpart in
the "itertools" module because it cumulatively performs an operation
on all the iterable’s elements and therefore can’t be applied to
infinite iterables. "func" must be a function that takes two elements
and returns a single value. "reduce()" takes the first two elements A
and B returned by the iterator and calculates "func(A, B)".  It then
requests the third element, C, calculates "func(func(A, B), C)",
combines this result with the fourth element returned, and continues
until the iterable is exhausted.  If the iterable returns no values at
all, a "TypeError" exception is raised.  If the initial value is
supplied, it’s used as a starting point and "func(initial_value, A)"
is the first calculation.

>>> import operator
>>> reduce(operator.concat, ['A', 'BB', 'C'])
'ABBC'
>>> reduce(operator.concat, [])
Traceback (most recent call last):
  ...
TypeError: reduce() of empty sequence with no initial value
>>> reduce(operator.mul, [1,2,3], 1)
6
>>> reduce(operator.mul, [], 1)
1

If you use "operator.add()" with "reduce()", you’ll add up all the
elements of the iterable.  This case is so common that there’s a
special built-in called "sum()" to compute it:

>>> reduce(operator.add, [1,2,3,4], 0)
10
>>> sum([1,2,3,4])
10
>>> sum([])
0

For many uses of "reduce()", though, it can be clearer to just write
the obvious "for" loop:

   # Instead of:
   product = reduce(operator.mul, [1,2,3], 1)

   # You can write:
   product = 1
   for i in [1,2,3]:
       product *= i

"enumerate(iter)" counts off the elements in the iterable, returning
2-tuples containing the count and each element.

>>> for item in enumerate(['subject', 'verb', 'object']):
...     print item
(0, 'subject')
(1, 'verb')
(2, 'object')

"enumerate()" はよく、リストに対してループさせて、条件に合う所に印を付
けていくときに使われます:

   f = open('data.txt', 'r')
   for i, line in enumerate(f):
       if line.strip() == '':
           print 'Blank line at line #%i' % i

"sorted(iterable, [cmp=None], [key=None], [reverse=False])" collects
all the elements of the iterable into a list, sorts the list, and
returns the sorted result.  The "cmp", "key", and "reverse" arguments
are passed through to the constructed list’s ".sort()" method.

   >>> import random
   >>> # Generate 8 random numbers between [0, 10000)
   >>> rand_list = random.sample(range(10000), 8)
   >>> rand_list
   [769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
   >>> sorted(rand_list)
   [769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
   >>> sorted(rand_list, reverse=True)
   [9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]

(For a more detailed discussion of sorting, see the Sorting mini-HOWTO
in the Python wiki at https://wiki.python.org/moin/HowTo/Sorting.)

The "any(iter)" and "all(iter)" built-ins look at the truth values of
an iterable’s contents.  "any()" returns "True" if any element in the
iterable is a true value, and "all()" returns "True" if all of the
elements are true values:

>>> any([0,1,0])
True
>>> any([0,0,0])
False
>>> any([1,1,1])
True
>>> all([0,1,0])
False
>>> all([0,0,0])
False
>>> all([1,1,1])
True


小さな関数とラムダ式
====================

関数型スタイルのプログラムを書いていると、述語として働いたり、何らかの
形で要素をつなぎ合わせたりするミニサイズの関数を必要とすることがよくあ
ります。

ちょうど良い関数がビルトインやモジュールで存在していれば、新しい関数を
定義する必要はまったくありません:

   stripped_lines = [line.strip() for line in lines]
   existing_files = filter(os.path.exists, file_list)

If the function you need doesn’t exist, you need to write it.  One way
to write small functions is to use the "lambda" statement.  "lambda"
takes a number of parameters and an expression combining these
parameters, and creates a small function that returns the value of the
expression:

   lowercase = lambda x: x.lower()

   print_assign = lambda name, value: name + '=' + str(value)

   adder = lambda x, y: x+y

もう一つの選択肢は、ふつうに "def" 文で関数を定義するだけです:

   def lowercase(x):
       return x.lower()

   def print_assign(name, value):
       return name + '=' + str(value)

   def adder(x,y):
       return x + y

どちらのほうが良いのでしょうか。それは好みの問題です; 著者のスタイルと
してはできるだけ "lambda" を使わないようにしています。

One reason for my preference is that "lambda" is quite limited in the
functions it can define.  The result has to be computable as a single
expression, which means you can’t have multiway "if... elif... else"
comparisons or "try... except" statements.  If you try to do too much
in a "lambda" statement, you’ll end up with an overly complicated
expression that’s hard to read.  Quick, what’s the following code
doing?

   total = reduce(lambda a, b: (0, a[1] + b[1]), items)[1]

わかるにはわかるでしょうが、何がどうなっているのか紐解いていくには時間
がかかるはずです。短い "def" 文で入れ子にすると、少し見通しが良くなり
ますが:

   def combine (a, b):
       return 0, a[1] + b[1]

   total = reduce(combine, items)[1]

でも単純に "for" ループにすれば良かったのです:

   total = 0
   for a, b in items:
       total += b

あるいは "sum()" ビルトインとジェネレータ式でも良いですね:

   total = sum(b for a,b in items)

Many uses of "reduce()" are clearer when written as "for" loops.

Fredrik Lundh は以前 "lambda" 利用のリファクタリングに関して以下の指針
を提案したことがあります:

1. ラムダ関数を書く。

2. そのラムダが一体ぜんたい何をしているのかコメントで説明する。

3. そのコメントをしばらく研究して、本質をとらえた名前を考える。

4. ラムダをその名前で def 文に書き換える。

5. コメントを消す。

著者はこの指針を本当に気に入っていますが、こうしたラムダなしスタイルが
他より優れているかどうかについて、異論は認めます。


itertools モジュール
====================

"itertools" モジュールには、よく使うイテレータや、イテレータ同士の連結
に使う関数がたくさん含まれています。この章では、そのモジュールの内容を
小さな例で紹介していきたいと思います。

このモジュールの関数を大まかに分けるとこうなります:

* 既存のイテレータに基づいて新しいイテレータを作る関数。

* イテレータの要素を引数として扱う関数。

* イテレータの出力から一部を取り出す関数。

* イテレータの出力をグループ分けする関数。


新しいイテレータを作る
----------------------

"itertools.count(n)" returns an infinite stream of integers,
increasing by 1 each time.  You can optionally supply the starting
number, which defaults to 0:

   itertools.count() =>
     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
   itertools.count(10) =>
     10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

"itertools.cycle(iter)" saves a copy of the contents of a provided
iterable and returns a new iterator that returns its elements from
first to last.  The new iterator will repeat these elements
infinitely.

   itertools.cycle([1,2,3,4,5]) =>
     1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

"itertools.repeat(elem, [n])" returns the provided element "n" times,
or returns the element endlessly if "n" is not provided.

   itertools.repeat('abc') =>
     abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ...
   itertools.repeat('abc', 5) =>
     abc, abc, abc, abc, abc

"itertools.chain(iterA, iterB, ...)" takes an arbitrary number of
iterables as input, and returns all the elements of the first
iterator, then all the elements of the second, and so on, until all of
the iterables have been exhausted.

   itertools.chain(['a', 'b', 'c'], (1, 2, 3)) =>
     a, b, c, 1, 2, 3

"itertools.izip(iterA, iterB, ...)" takes one element from each
iterable and returns them in a tuple:

   itertools.izip(['a', 'b', 'c'], (1, 2, 3)) =>
     ('a', 1), ('b', 2), ('c', 3)

It’s similar to the built-in "zip()" function, but doesn’t construct
an in-memory list and exhaust all the input iterators before
returning; instead tuples are constructed and returned only if they’re
requested.  (The technical term for this behaviour is lazy
evaluation.)

このイテレータの用途には、すべて同じ長さのイテラブルを想定しています。
長さが違っていれば、出力されるストリームは一番短いイテラブルと同じ長さ
になります。

   itertools.izip(['a', 'b'], (1, 2, 3)) =>
     ('a', 1), ('b', 2)

とは言え、これをやってしまうと長いイテレータから要素をひとつ無駄に多く
取って捨ててしまうかもしれませんので、やめておいたほうが良いです。その
捨てられた要素を抜かしてしまう危険があるので、もうそのイテレータはそれ
以上使えなくなってしまいます。

"itertools.islice(iter, [start], stop, [step])" returns a stream
that’s a slice of the iterator.  With a single "stop" argument, it
will return the first "stop" elements.  If you supply a starting
index, you’ll get "stop-start" elements, and if you supply a value for
"step", elements will be skipped accordingly.  Unlike Python’s string
and list slicing, you can’t use negative values for "start", "stop",
or "step".

   itertools.islice(range(10), 8) =>
     0, 1, 2, 3, 4, 5, 6, 7
   itertools.islice(range(10), 2, 8) =>
     2, 3, 4, 5, 6, 7
   itertools.islice(range(10), 2, 8, 2) =>
     2, 4, 6

"itertools.tee(iter, [n])" replicates an iterator; it returns "n"
independent iterators that will all return the contents of the source
iterator. If you don’t supply a value for "n", the default is 2.
Replicating iterators requires saving some of the contents of the
source iterator, so this can consume significant memory if the
iterator is large and one of the new iterators is consumed more than
the others.

   itertools.tee( itertools.count() ) =>
      iterA, iterB

   where iterA ->
      0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

   and   iterB ->
      0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...


要素に対して関数を呼ぶ
----------------------

Two functions are used for calling other functions on the contents of
an iterable.

"itertools.imap(f, iterA, iterB, ...)" returns a stream containing
"f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]),
...":

   itertools.imap(operator.add, [5, 6, 5], [1, 2, 3]) =>
     6, 8, 8

The "operator" module contains a set of functions corresponding to
Python’s operators.  Some examples are "operator.add(a, b)" (adds two
values), "operator.ne(a, b)" (same as "a!=b"), and
"operator.attrgetter('id')" (returns a callable that fetches the
""id"" attribute).

"itertools.starmap(func, iter)" assumes that the iterable will return
a stream of tuples, and calls "f()" using these tuples as the
arguments:

   itertools.starmap(os.path.join,
                     [('/usr', 'bin', 'java'), ('/bin', 'python'),
                      ('/usr', 'bin', 'perl'),('/usr', 'bin', 'ruby')])
   =>
     /usr/bin/java, /bin/python, /usr/bin/perl, /usr/bin/ruby


要素を選択する
--------------

さらに別のグループとして、述語 (predicate) に基づいてイテレータの要素
からサブセットを選び出す関数があります。

"itertools.ifilter(predicate, iter)" returns all the elements for
which the predicate returns true:

   def is_even(x):
       return (x % 2) == 0

   itertools.ifilter(is_even, itertools.count()) =>
     0, 2, 4, 6, 8, 10, 12, 14, ...

"itertools.ifilterfalse(predicate, iter)" is the opposite, returning
all elements for which the predicate returns false:

   itertools.ifilterfalse(is_even, itertools.count()) =>
     1, 3, 5, 7, 9, 11, 13, 15, ...

"itertools.takewhile(predicate, iter)" returns elements for as long as
the predicate returns true.  Once the predicate returns false, the
iterator will signal the end of its results.

   def less_than_10(x):
       return (x < 10)

   itertools.takewhile(less_than_10, itertools.count()) =>
     0, 1, 2, 3, 4, 5, 6, 7, 8, 9

   itertools.takewhile(is_even, itertools.count()) =>
     0

"itertools.dropwhile(predicate, iter)" discards elements while the
predicate returns true, and then returns the rest of the iterable’s
results.

   itertools.dropwhile(less_than_10, itertools.count()) =>
     10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

   itertools.dropwhile(is_even, itertools.count()) =>
     1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...


要素をグループ分けする
----------------------

The last function I’ll discuss, "itertools.groupby(iter,
key_func=None)", is the most complicated.  "key_func(elem)" is a
function that can compute a key value for each element returned by the
iterable.  If you don’t supply a key function, the key is simply each
element itself.

"groupby()" collects all the consecutive elements from the underlying
iterable that have the same key value, and returns a stream of
2-tuples containing a key value and an iterator for the elements with
that key.

   city_list = [('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL'),
                ('Anchorage', 'AK'), ('Nome', 'AK'),
                ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ'),
                ...
               ]

   def get_state ((city, state)):
       return state

   itertools.groupby(city_list, get_state) =>
     ('AL', iterator-1),
     ('AK', iterator-2),
     ('AZ', iterator-3), ...

   where
   iterator-1 =>
     ('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL')
   iterator-2 =>
     ('Anchorage', 'AK'), ('Nome', 'AK')
   iterator-3 =>
     ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ')

"groupby()" assumes that the underlying iterable’s contents will
already be sorted based on the key.  Note that the returned iterators
also use the underlying iterable, so you have to consume the results
of iterator-1 before requesting iterator-2 and its corresponding key.


functools モジュール
====================

Python 2.5 からの "functools" モジュールには、高階関数がいくつか入って
います。 **高階関数** とは、入力として関数を受け取って新たな関数を返す
関数です。このモジュールで一番便利なツールは "functools.partial()" 関
数です。

関数型スタイルのプログラムでは時折、既存の関数から一部のパラメータを埋
めた変種を作りたくなることがあります。Python の関数 "f(a, b, c)" とい
うものがあるとしてください; "f(1, b, c)" と同じ意味の "g(b, c)" という
関数を作りたくなることがあります; つまり "f()" のパラメータを一つ埋め
るわけです。これは「関数の部分適用」と呼ばれています。

The constructor for "partial" takes the arguments "(function, arg1,
arg2, ... kwarg1=value1, kwarg2=value2)".  The resulting object is
callable, so you can just call it to invoke "function" with the
filled-in arguments.

以下にあるのは、小さいけれども現実的な一つの例です:

   import functools

   def log (message, subsystem):
       "Write the contents of 'message' to the specified subsystem."
       print '%s: %s' % (subsystem, message)
       ...

   server_log = functools.partial(log, subsystem='server')
   server_log('Unable to open socket')


operator モジュール
-------------------

"operator" モジュールは、既に取り上げましたが、Python の演算子に対応す
る関数が入っているモジュールです。関数型スタイルのコードにおいて、演算
を一つ実行するだけのくだらない関数を書かずに済むので、よく世話になりま
す。

このモジュールの関数を一部だけ紹介しましょう:

* Math operations: "add()", "sub()", "mul()", "div()", "floordiv()",
  "abs()", …

* 論理演算子: "not_()", "truth()"

* ビット演算子: "and_()", "or_()", "invert()"

* 比較: "eq()", "ne()", "lt()", "le()", "gt()", "ge()"

* オブジェクト識別: "is_()", "is_not()"

ちゃんとした一覧は operator モジュールの文書でご覧ください。


更新履歴と謝辞
==============

著者は提案の申し出や修正、様々なこの記事の草稿の助けをしてくれた以下の
人々に感謝します: Ian Bicking, Nick Coghlan, Nick Efford, Raymond
Hettinger, Jim Jewett, Mike Krell, Leandro Lameiro, Jussi Salmela,
Collin Winter, Blake Winton.

Version 0.1: posted June 30 2006.

Version 0.11: posted July 1 2006.  Typo fixes.

Version 0.2: posted July 10 2006.  Merged genexp and listcomp sections
into one. Typo fixes.

Version 0.21: Added more references suggested on the tutor mailing
list.

Version 0.30: Adds a section on the "functional" module written by
Collin Winter; adds short section on the operator module; a few other
edits.


参考資料
========


一般論
------

Harold Abelson と Gerald Jay Sussman, Julie Sussman による **Structure
and Interpretation of Computer Programs**。
https://mitpress.mit.edu/sicp/ に全文があります。この計算機科学に関す
る古典的な教科書では、2 章と 3 章でデータフローをプログラム内でまとめ
るためのシーケンスとストリームの利用について議論しています。この本は例
として Scheme を使っていますが、これらの章内の多くのデザインアプローチ
は関数スタイルな Python コードにも適用できます。

http://www.defmacro.org/ramblings/fp.html: 関数プログラミングの一般的
な入門で Java での例を利用していて、長大な歴史の紹介があります。

https://en.wikipedia.org/wiki/Functional_programming: 関数プログラミン
グに関する一般的な内容の記事。

https://en.wikipedia.org/wiki/Coroutine: コルーチンに関する記事。

https://en.wikipedia.org/wiki/Currying: カリー化の概念に関する記事。


Python 特有の話
---------------

http://gnosis.cx/TPiP/: David Mertz’s の本の最初の章 *Text Processing
in Python* では文書処理のための関数プログラミングについて議論していま
す、この議論の節には 「Utilizing Higher-Order Functions in Text
Processing」 というタイトルがついています。

Mertz also wrote a 3-part series of articles on functional programming
for IBM’s DeveloperWorks site; see

part 1, part 2, and part 3,


Python 文書
-----------

"itertools" モジュールの文書。

"operator" モジュールの文書。

**PEP 289**: 「Generator Expressions」

**PEP 342**: 「Coroutines via Enhanced Generators」 describes the new
generator features in Python 2.5.
