Python における関数型プログラミング のための functools, itertools (1) – Haskell と同じ名前の関数たち

1. 関数型プログラミングのための functools, itertools モジュール

Python 2.7

Python の標準ライブラリには、関数型プログラミングにとって重要なモジュールがある。

• 9.7. itertools — Functions creating iterators for efficient looping
• 9.8. functools — Higher-order functions and operations on callable objects

itertools, functools は、

• The Python Standard Library — Python v2.7.3 documentation
  • 9. Numeric and Mathematical Modules

の階層の中にある。

The Python Standard Library — Python v2.7.3 documentation via kwout

9. Numeric and Mathematical Modules には、これまで何度か見た decimal モジュールが含まれる。

• cf. Python で正確な小数の計算をする

Python には、限定的ではあるけれど、関数型プログラミングをサポートしており、Haskell などから借りてきた 2 つのモジュールがある。

Python - Wikipedia によると、

The design of Python offers limited support for functional programming in the Lisp tradition. However, there are significant parallels between the philosophy of Python and that of minimalist Lisp-family languages such as Scheme. The library has two modules (itertools and functools) that implement proven functional tools borrowed from Haskell and Standard ML.^[64]

^{(太字は引用者による)}

functools, itertools の関数については、これまでに 2 つ試した。

• Python で部分適用 --- functools.partial
• Python でリスト内のリストを連結 --- itertools.chan

 

Python 3.2

追記（2012/05/22）： Python 3.2 では、9. Functional Programming Modules が 8. Numeric and Mathematical Modules から独立している。

The Python Standard Library — Python v3.2.3 documentation via kwout

 

2. functools, itertools モジュールの関数名は、Haskell の関数名に似ている

itertools のドキュメントにざっと目を通すと、関数の名前に親近感を感じる。(@_@) Haskell に同じ名前の関数がある。

Haskell の分類に倣い、関数を分類すると、

• 無限リスト
  • cycle
  • repeat
• 部分リスト
  • takewhile
  • dropwhile
• 要素のグループ化
  • groupby

上記は、全て itertools の関数なので、

イテレータ

が絡んでくる。

• cf. Python のイテレータ

 

3. 無限リストを扱う

cycle

cycle 関数は、コンテナオブジェクトから要素を取り出す。

引数は `iterable’ .

itertools.cycle(iterable)

引数の iterable は、反復可能オブジェクトのこと。

E. 用語集 によると、

反復可能オブジェクト (iterable)

コンテナオブジェクトで、コンテナ内のメンバを一つづつ返せるようになっているものです。

簡単に言うと、子どもである要素を管理する、親みたいなオブジェクト。

反復可能オブジェクトの例には、 (list、str、および tuple といった) 全ての配列型や、dict や file といった非配列型、あるいは __iter__() や __getitem__() メソッドを実装したクラスのインスタンスが含まれます。…

イテレータ (iterator)、 配列 (sequence)、および ジェネレータ (generator) も参照してください。(同上より)

上記に関しては、以下を参照。

• シーケンス型に慣れる
• イテレータ (1)
• ジェネレータ (1) - 動作を試す
• 要素を添字で参照する - 特殊メソッドを使って

cycle 関数は、引数に渡された、反復可能なオブジェクトを、無限に繰り返すためのイテレータを返す。例えば、range 関数で数値のリストを作り、そこから無限に要素を取り出す。

from itertools import *

it = cycle(range(4))
for i in range(10):
    print it.next(),     # 0 1 2 3 0 1 2 3 0 1

Python では、無限リストを扱うために、イテレータで要素を１つずつ取り出すことにより実現している。

Haskell の cycle の書き方は、以下の通り。

*Main> take 10 $ cycle [0..3]
[0,1,2,3,0,1,2,3,0,1]

以降、Python のコードは、上記と同一モジュールに書くので、import は省略する。

 

repeat

repeat 関数の引数には、オブジェクトを渡す。 iterable である必要はない。

cycle と違いは、オプションとして、繰り返す回数を指定することができる。

for x in repeat('A', 10):
    print x,            #  A A A A A A A A A A 

リスト内包表記で書くと、

print [x for x in repeat('A',10)]

Haskell における repeat は、次のように書く。

*Main> take 10 $ repeat 'A'
"AAAAAAAAAA"

 

4. 部分リストを取得する

takewhile と dropwhile は、述語が真の間、それぞれ要素を take または drop する。引数は iterable .

for x in takewhile(lambda x: x < 5, range(10)):
    print x,             # 0 1 2 3 4

for x in dropwhile(lambda x: x < 5, range(10)):
    print x,             # 5 6 7 8 9

Haskell では、takeWhile の `w’ は大文字なのに対して、Python は小文字であることに注意。

先ほどと同じくリスト内包表記を使うと、

print [x for x in takewhile(lambda x: x < 5, range(10))]
print [x for x in dropwhile(lambda x: x < 5, range(10))]

この関数の説明には predicate （述語）という言葉が使われていた。

Make an iterator that returns elements from the iterable as long as the predicate is true.

(takewhile の説明より)

述語に関しては、以下を参照。

• cf. Haskell の Prelude 散策 (2) - 述語

 

Haskell の場合

Haskell の takeWhile と dropwhile は、以下の通り。

*Main> takeWhile (< 5) [0..10]
[0,1,2,3,4]

*Main> dropWhile (< 5) [0..10]
[5,6,7,8,9,10]

 

5. 要素のグループ化

groupby

groupby 関数は、反復可能なオブジェクトを渡すと、要素をグループ化してくれる。

groupby の `b’ は小文字であることに注意。

for k,g in groupby([1,2,2,3,3,3,4,5,5]):
    print k, list(g)

結果は、グループ化したときのキーと、その要素がリストとして返される。

1 [1]
2 [2, 2]
3 [3, 3, 3]
4 [4]
5 [5, 5]

オプションとして関数を渡すと、返されるキーを変更することができる。

for k,g in groupby([1,2,2,3,3,3,4,5,5], lambda x: str(x)+":hoge"):
    print k

結果は、

1:hoge
2:hoge
3:hoge
4:hoge
5:hoge

 

Haskell の group と groupBy

Haskell では、 Data.List に groupBy がある。

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

group 関数は、groupBy の特殊な関数。

The groupBy function is the non-overloaded version of group.

group 関数の型を確認しておく。

group :: Eq a => [a] -> [[a]]

型を見ると、関数の引数の制約は、EQ クラスのインスタンスであること。 group 関数は、同値検査によって要素がグループ化される。

Prelude Data.List> group [1,2,2,3,3,3,4,5,5]
[[1],[2,2],[3,3,3],[4],[5,5]]

これに対して、groupBy 関数は、より汎用的になっている。要素をグループ化するときの基準となる関数を第 1 引数に与える。

Prelude Data.List> groupBy (\x y -> x == y) [1,2,2,3,3,3,4,5,5]
[[1],[2,2],[3,3,3],[4],[5,5]]

または、次のように書ける。

Prelude Data.List> groupBy (==) [1,2,2,3,3,3,4,5,5]
[[1],[2,2],[3,3,3],[4],[5,5]]

グループ化する基準を関数で与えることができるので、次のように、複雑な基準でグループ化できる。

Prelude Data.List> groupBy (\x y -> x+1 == y) [1,2,2,3,3,3,4,5,5]
[[1,2,2],[3],[3],[3,4],[5],[5]]

 

6. その他の関数

functools, itertools の中には、上記以外に関数が存在する。名前を列挙すると、

1. 全く動作の想像がつかないものから、
2. map, filter, zip, slice のようなお馴染みの関数に接頭辞 `i’ が付いたものや、
3. combinations, permutations, product のように具体的な計算の意味が分かるものまで様々。

• functools
  • update_wrapper
  • wraps
• itertools
  • count
  • ifilter
  • ifilterfalse
  • imap
  • islice
  • izip
  • tee
  • version 2.6
    • starmap
    • from_iterable
    • izip_longest
    • combinations
    • permutations
    • product

Python で部分適用 - functools モジュールの partial 関数

1. Python は一部の引数を与えて関数を呼び出すことができない

Haskell では、関数に複数の引数があるとき、先に一部の引数のみ渡しておき、後から残りの引数を渡すことができる。一部の引数を与えることを「部分適用」と言う。

Python では、普通そういうことはできない。例えば、３つの引数を足し合わせる関数 addThree 関数に対して、１つの引数だけ与える。

def addThree(a,b,c):
    return a + b + c

print addThree(1)

上記を実行すると、引数が足りないとエラーが表示される。

exceptions.TypeError: addThree() takes exactly 3 arguments (1 given)

 

2. functools の partial 関数で部分適用

6.6 functools モジュールの partial 関数を使うと、部分適用を利用できる。

partial(func[,*args][, **keywords])

Return a new partial object which when called will behave like func called with the positional arguments args and keyword arguments keywords.

例えば、先ほど定義した addThree 関数に対して、partial 関数を使い、引数を１つだけ与える。

import functools

addTwo = functools.partial(addThree,1)
print addTwo(2,3)

partial 関数により、addThree 関数の最初の引数だけ渡した関数 addTwo を作成した。その後、addTwo 関数に対して、残りの二つの引数を与えている。

以下では、部分適用をした結果から、更に部分適用した addOneFromTwo 関数を作成し、元の addThree に二つ引数を渡した関数 addOne を定義した。

addOneFromTwo = functools.partial(addTwo,2)
print addOneFromTwo(3)

addOne = functools.partial(addThree,1,2)
print addOne(3)

部分適用により、予め抽象的な関数を定義しておき、部分適用によって具体的な関数を導くことができる。上手く使えば、関数のモジュール化 を促進できる。

 

キーワード引数を利用して

キーワード引数を使うと、部分適用するときの引数を特定できる。

addTwo_ = functools.partial(addThree,c=3)
print addTwo_(1,2)

addOne_ = functools.partial(addTwo_,a=1)
print addOne_(b=2)

addOneFromTwo = functools.partial(addThree,a=1,c=3)
print addOneFromTwo(b=2)

 

3. reduce 関数に対して部分適用し、具体的な関数を導く

リストの要素を足し合わせる sum 関数は、畳み込み関数 reduce より導くことができる。

なぜ関数プログラミングは重要か によると、

sum = reduce add 0

reduce 関数に対して、部分適用することによって sum を定義している。

Python の reduce 関数の使い方は、

print reduce(lambda a,b: a+b, [1,2,3,4,5])

reduce 関数に対して部分適用を利用し、シーケンスを後で与えるようにして、sum 関数を定義してみる。

L = [1,2,3,4,5]

import operator
from functools import partial

# 合計
mysum = partial(reduce, operator.add)
print mysum(L)

(functools.partial と書くのが面倒だったので、import の仕方を変更した。)

上記の書き方から、sum 関数が reduce というメタ的な関数の特殊パターンであるという雰囲気が伝わって来る。

• cf. Python で合計

Python では、(+) のように、二項演算子を渡すことができないので、3.10 operator モジュールの add を利用した。

 

4. 関数を合成する関数を定義

Haskell の 関数を合成する(.) 関数を、partial を使い Python  で定義してみる。

• cf. Haskell の関数合成

関数を合成する関数名を `c’ とした。

• cf. function composition

c = lambda f,g: partial(lambda f,g,h: f(g(h)), f, g)

def … return で定義した方が読みやすいかな。

def c(f,g):
    return partial(lambda f,g,h: f(g(h)), f, g)

それとも、関数をネストして定義してみる。

def c(f,g):
    def _(f,g,h):
        return f(g(h))
    return partial(_,f,g)

c 関数を使ってみる。

add3 = lambda x: x+3
mul3 = lambda x: x*3

print c(add3,mul3)(10)   # 33
print c(mul3,add3)(10)   # 39

 

関連記事

• Python でリスト内包表記を使ってクイックソート
• Python の map, filter, reduce とリスト内包表記
• Haskell の Prelude 散策 (1) - リスト操作 : 要素の重ね合わせ (folds)
• Haskell の部分適用 (2)

Haskell を学ぶための環境を整える

ふつうのHaskell
プログラミング

1. 最近気になる「関数型言語」

新しい言語を勉強しようと思う。最近の流行を調べたら、

関数型言語

がホットなようだ。以前から List や Scheme には興味があった。しかし、敷居が高くて手をつけることができなかった。

Haskell

最近、Haskell の入門書が出版された。この本を手始めにして、Haskell を学ぶことにした。

 

Erlang

Haskell 以外に、関数型言語として注目されているのは Erlang 。

twitterブームの陰で注目を集める"Erlang" － ＠IT によると、

twitterでは、メッセージングシステムに"ejabberd"を使っているという。これは"Erlang"で書かれたIMサーバだ。

Erlangは並列処理に適したプログラミング言語で、1987年に登場し、1998年にはオープンソース化されているので新しく登場した言語というわけではないが、時流に乗る形で、現在にわかに注目を集め始めている。Rubyの開発者として知られる、まつもとゆきひろ氏も、4月18日の" 「次」の言語"と題したブログのエントリで「次にくるトレンドは『関数型』と『並列』。両方を押さえたErlangが本命。歴史も信頼性もあり、知名度上昇中」と、次にメジャーになりうる言語の本命にErlangの名前を挙げている。

このような評価を目にしたことも、関数型言語をはじめようとしたキッカケとなった。

 

OCaml

入門OCaml

Haskell と並んで気になるのは、

Objective Caml

できれば OCaml プログラミング入門 も読んでみたい。

 

最初に読みたい論文

関数型言語を学ぶなら、

• なぜ関数プログラミングは重要か

は押えておきたい。

 

2. コンパイラのインストール

以下のいずれかをインストール。

• Haskell Platform
• The Glasgow Haskell Compiler

 

3. Emacs の設定

Haskell を書くためのエディタとして Emacs を利用する。Windows 上では Meadow を使った。

• Emacs | Haskell | OpenSource Web

を参考に

haskell-mode

の設定をした。load-path を自分の環境に合わせて変更した。

haskell-mode

Haskell Mode for Emacs によると、haskell-mode は Emacs Lisp packages から最新のものを取得できるとのこと。インストールの方法については、以下を参照。

• A guide on how to install and customise the mode

haskell-mode からダウンロードしたファイルを解凍して、フォルダ名を haskell-mode に変更。 C:\meadow\site-lisp に配置した。

~/.emacs には、以下を追加。

(load "/meadow/site-lisp/haskell-mode-2.4/haskell-site-file")
(add-hook 'haskell-mode-hook 'turn-on-haskell-doc-mode)
(add-hook 'haskell-mode-hook 'turn-on-haskell-indent)

追記 (2009.12.27) :  Dropbox に Emacs のライブラリを置いたのに伴い、haskell-mode も Dropbox に置くことに。上記の load … の一文を次のように書き換えた。

(load "~/My Documents/My Dropbox/elisp/haskell-mode/haskell-site-file.el")

haskell-mode 使える関数を予め describe-mode で確認しておくと良い。

• cf. Emacs で利用中のモードに関するヘルプを表示する

 

4. Emacs でプログラムの実行

コンパイルする場合

プログラムをコンパイルするには、今マンドラ以上で、

ghc プログラム名 -o プログラム名

(プログラムの拡張子は、.hs を用いる。)

Emacs では、M-! または M-| を入力した後、Shell command から行う。

プログラムを実行するには、Shell command から、

プログラム名

を入力する。

 

ghci を利用する場合

プログラムの実行結果をすぐに見たいときは、コンパイルしない。

Shell command から

runghc プログラム名

とすると、実行させることができる。

Emacs を利用している場合、

C-c C-l

により、GHCi が起動する。runghc よりも楽にプログラムを実行できる。

追記 (2009.12.21) : 新しいバージョンをインストールした直後に C-c C-l すると、

… no such file or directory, hugs

というエラーが表示される。この場合、ghci へのパスを設定した後、再ログインし、新しい ghci へのパスをプログラムが認識できるようにする必要がある。