[Python] Haskellのキモいフィボナッチ数列をPythonで書いてみる

皆さんはHaskellのキモいフィボナッチ数列を知っていますか？

fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)

無限リストの生成に自分自身を利用している所が，関数型言語っぽい書き方みたいです．Haskellのキモいフィボナッチ数列がやっと理解できたからこれでもかという程に細かく説明してみた #Haskellを読んでなんとなく理解できたので，さっそくPythonで書き直してみたいと思います．

作成したコード

とりあえず最初に書いたコードを示しておきます．

from itertools import chain, islice
from operator import add

def fib():
    yield from chain([0, 1], map(add, fib(), islice(fib(), 1, None)))

どうでしょうか？Pythonで実装した割には，それっぽいコードになっていると思います．
利用時の注意点ですが，fib()は無限に値を生成するジェネレータ関数なので，以下のように利用すると無限ループしてしまいます．

for n in fib():
    print(n)

そのためitertools.islice()でのスライスや，for文の途中でのbreakが必要です．

print(*islice(fib(), 10))

for i, n in enumerate(fib()):
    print(n)
    if i >= 10:
        break

ちなみにこのコードですが，再帰で生成されるジェネレータが指数的に増えるため，残念ながら実用的ではないです．．．
以下の実装をオススメします．

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

性能は悪いですが，見た目がいい感じで原作(Haskell)に忠実？なので私はとても気に入ってます．

fib = 0:1:zipWith (+) fib (tail fib)

def fib():
    yield from chain([0, 1], map(add, fib(), islice(fib(), 1, None)))

では，これからこのコードについて解説していきたいと思います．

最初に書いたコード

Haskellっぽくフィボナッチ数列を書きつつIEnumerableの評価タイミングを確認のLINQのコードを参考に，最初にこのようなコードを書きました．

def fib():
    yield 0
    yield 1
    for n in (a + b for a, b in zip(fib(), islice(fib(), 1, None))):
        yield n

はじめの要素を飛ばしたイテレータの取得のために，itertools.islice()を利用しています．ジェネレータは無限に続くため，リストにしてからスライスをするような全体を先に評価する処理はできません．

for n in (a + b for a, b in zip(fib(), list(fib())[1:])):    # これはできない

for文を短くしたい

現在のコードはzip()してからジェネレータ式でタプルの加算をしているため，少し冗長です．そこで，HaskellのzipWithと同様の動作をするPythonの関数を探した所，map()は複数のイテレータを引数に取れることが分かりました．operator.add()と合わせて利用することで，in以下を短縮します．

def fib():
    yield 0
    yield 1
    for n in map(add, fib(), islice(fib(), 1, None)): 
        yield n

for文でのyieldが気に入らない

ジェネレータから生成される値をfor文で一つ一つyieldしているところが気に入らなかったのですが，Python3.3からはサブジェネレータにジェネレータの操作の一部を委譲できる，yield fromという素敵な構文があるみたいです．これを使って先程のコードを書き換えると

def fib():
    yield from[0, 1]
    yield from map(add, fib(), islice(fib(), 1, None))

のようにシンプルになります．
そして，itertools.chain()で全体の連結を行って完成です!!!!!

def fib():
    yield from chain([0, 1], map(add, fib(), islice(fib(), 1, None)))

せっかくなのでワンライナーにしてみる

関数定義部分を合わせると2行になってしまっているので，lambdaを使ってワンライナーにしてみたいと思います．
再帰を利用したコードのワンライナーは，闇Pythonista入門(Pythonワンライナーのテクニック集)を参考にしました．

fib = (lambda f: f(f))(lambda f: (yield from chain([0, 1], map(add, f(f), islice(f(f), 1, None)))))

自分自身を引数で受け取るlambdaで再帰を実現しています．ここまで来ると原型を留めていないですね．．．

おわりに

最初はここまでいい感じに書けると思っていなかったので，自分でも驚いています．このフィボナッチ数列のコードは性能が悪いので実用性は無いですが，itertoolsやジェネレータ・イテレータについての理解が深まったので良しとします．
いい感じにフィボナッチ数列を書けた方がいれば，コメントで紹介して頂けると非常に嬉しいです．