Re: 関数プログラミングのアプローチ (6) 前半

関数プログラミングのアプローチ (6) - lethevert is a programmer
http://d.hatena.ne.jp/lethevert/20071027/p1

咀嚼中。
__next__のような2つのアンダーバーで囲まれたメソッドはPython処理系が特殊な意味のメソッドを実装するためのものなので勝手に使うのはあんまりよくない。Pythonの無限リストを作るのかと勘違いした。
Pythonの無限リストは「あるオブジェクトが内部状態を変更しながらnextが呼ばれるたびに次の値を返していく」ってものだから、もちろん関数型言語の文脈での無限リストとは別のもの。

LazyListクラスがとてもリストっぽくないけど、これってようするに「__next__が最初に呼ばれるときまで評価を遅延させるもの」だよね。説明の流れからサンクという言葉を出したくなかったのかと思うけど、僕は自分が咀嚼したいだけだからサンクに変えちゃう。

# -*- coding: cp932 -*-
class Thunk(object):
    def __init__(self, func):
        self.is_defined = False
        self.func = func
    def __call__(self):
        if not self.is_defined:
            self.value = self.func()
            self.is_defined = True
        return self.value

def one():
    "評価されるとone!と叫んで1を返す"
    print "one!"
    return 1

t = Thunk(one)

print t()
# one!
# 1

print t()
# 1

で、下のように遅延リストが書ける。

def repeat(n):
    "与えられた数を繰り返す遅延リスト"
    def f():
        return (n, Thunk(f))
    return Thunk(f)

ls = repeat(1)
x, ls = ls()
print x # 1
x, ls = ls()
print x # 1

def count(n):
    "与えられた数からカウントアップする遅延リスト"
    def f(m):
        return (m, Thunk(lambda: f(m + 1)))
    return Thunk(lambda: f(n))

ls = count(1)
x, ls = ls()
print x # 1
x, ls = ls()
print x # 2

ちなみにrepeatとcountはPythonに標準で付いてきている無限リスト：5.15.1 Itertool関数の中での名前。

• • • • -

あ、そっか。lsはリスト的なものだと思ってしまうけど、そうではなくて「リストの次の値(ただしまだ評価していない)」なんだな。

next = count(1)
x, next = next()
print x # 1
x, next = next()
print x # 2

次があるかどうかは評価してみないとわからない。nextを呼んでみないとわからない。nextを呼んで次がなかったらNoneが返る。

• • • • -

後半。元々のThunkがnext()でNoneが返った(つまり「リストはもう残ってない」)時には何もしないで暗黙にNoneを返すようになっていたからそれに全部合わせてみたけど、読みやすさを考えると明示的にreturn Noneした方がいいのかも知れない。ちなみにPythonにはStopIterationって例外があるからこれを投げずに返してやってもいいかもしれない。

def mapL(func, next):
    def f(next):
        v = ls()
        if v:
            x, next = v
            return func(x), Thunk(lambda: f(next))

    return Thunk(lambda: f(ls))

def takeL(n, next):
    def f(n, next):
        if n <= 0:
            return None
        v = next()
        if v:
            x, next = v
            return x, Thunk(lambda: f(n - 1, next))

    return Thunk(lambda: f(n, next))

def forceList(next):
    ret = []
    v = next()
    while v:
        x, next = v
        ret.append(x)
        v = next()
    return ret

print forceList(takeL(5, count(5)))
# [5, 6, 7, 8, 9]

def groupL(n, next):
    def f(next):
        ret = []
        for i in range(n):
            v = next()
            if v:
                x, next = v
                ret.append(x)
            elif ret:
                return ret, Thunk(lambda: v)
            else:
                return v
        else:
            return ret, Thunk(lambda: f(next))

    return Thunk(lambda: f(next))

print forceList(takeL(3, groupL(3,count(5))))
# [[5, 6, 7], [8, 9, 10], [11, 12, 13]]

• • • • -

なるほど、(7)で乱数も無限リストだと言うためにああいうコードになっていたのか。よく考えられている…。

• • • • -

わー、(8)でThunkって名前に変わってる！

このコードは next(x)を実行すると遅延リストではなく 3 を返します。これは、1 + 2という計算の呼出を、next()が呼ばれるまで遅らせていると考えることができます。このようなデータ構造を一般的にThunkと呼びます。上の LazyListをThunkという名前に書き換えたものを、下に掲載します。