代数的データ型と FizzBuzz と

タイトルは意味不明です。

[PyAlgebraicDataTypes]
(https://github.com/benanhalt/PyAlgebraicDataTypes) を使って遊んでみました。Racket という言語に触発されて 代数的データ型 を Python で表現するといったライブラリのようです。学習向けに小さくて良さそうだったので試してみました。

3.4

>>> from adt import ADT, Require
>>> class List(ADT): pass
... 
>>> class Nil(List): pass
... 
>>> class Cons(List):
...   car = Require(int)
...   cdr = Require(List)

List は Nil と Cons から成るというのを表現するとこんな感じです。
空のリストは、

3.4

>>> Nil()
Nil()

要素をもつリストは、

3.4

>>> Cons(1, Cons(2, Nil()))
Cons(car=1, cdr=Cons(car=2, cdr=Nil()))

Cons.cdr に Cons を渡すことで表現できます。要素がないときは Nil にすることで終端を表現できます。

この List データを手で書くのは面倒なので引数で指定した要素をもつ range_ 関数を定義してみます。

3.4

>>> def range_(until, value=0):
...     return Nil() if value == until else Cons(value, range_(until, value + 1))
... 
>>> range_(5)
Cons(car=0, cdr=Cons(car=1, cdr=Cons(car=2, cdr=Cons(car=3, cdr=Cons(car=4, cdr=Nil())))))

自分でリストのデータ構造をもつ List 型を定義できました。

何となく使い方が分かったので Fizz Buzz 的なデータ構造をもつ FizzBuzzList を定義してみます。

3.4

class FizzBuzzList(List):
    pass

class Value(FizzBuzzList):
    value = Require(int)

class Fizz(FizzBuzzList):
    value = Require(int)

class Buzz(FizzBuzzList):
    value = Require(int)

class FizzBuzz(FizzBuzzList):
    value = Require(int)
    fizz = Require(Fizz)
    buzz = Require(Buzz)

FizzBuzzList は List の特性を受け継ぎ、Value、Fizz、Buzz、FizzBuzz から成ると定義します。先ほどと同様に Fizz Buzz なリストを返す fbrange も作ってみましょう。

3.4

def fbrange(until, value=0):
    """
    >>> fbrange(6, 1)  # doctest: +NORMALIZE_WHITESPACE
    Cons(car=Value(value=1), cdr=Cons(car=Value(value=2),
         cdr=Cons(car=Fizz(value=3), cdr=Cons(car=Value(value=4),
         cdr=Cons(car=Buzz(value=5), cdr=Nil())))))
    """
    def make_cons(obj):
        return Cons(obj, fbrange(until, obj.value + 1))

    if value == until:
        return Nil()
    elif value % 15 == 0:
        return make_cons(FizzBuzz(value, Fizz(value), Buzz(value)))
    elif value % 5 == 0:
        return make_cons(Buzz(value))
    elif value % 3 == 0:
        return make_cons(Fizz(value))
    return make_cons(Value(value))

データ構造としての Fizz Buzz を考えたときに、データを作るときにそのロジックが出てきます。ここでは一般的に言う Fizz Buzz のロジックで生成していますが、独自のロジックで Fizz Buzz のデータ構造を考えることもできますね。

[MatchCases]
(https://github.com/benanhalt/PyAlgebraicDataTypes#match-cases) を継承した matcher を作ることでパターンマッチを表現できます。このデータ構造をパターンマッチして Fizz Buzz を出力してみます。

3.4

from adt import MatchCases

class FizzBuzzMatch(MatchCases):
    def value(match: Value):
        return value
    def fizz(match: Fizz):
        return 'fizz'
    def buzz(match: Buzz):
        return 'buzz'
    def fizzbuzz(match: FizzBuzz):
        return FizzBuzzMatch(fizz) + FizzBuzzMatch(buzz)
    def cons(match: Cons):
        return '{}, {}'.format(FizzBuzzMatch(car), FizzBuzzMatch(cdr))
    def nil(match: Nil):
        return None

こんな感じ。

3.4

>>> FizzBuzzMatch(fbrange(16, 1))
'1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, None'

Python は動的型付けなのでパターンマッチ風に書いても実際のエラーは実行時にしか検出できないという意味では、以下のように isinstance で実装しても、この例では大きな差ではないかもしれません。

3.4

def match_fizzbuzz(fblist):
    if isinstance(fblist, Value):
        return fblist.value
    elif isinstance(fblist, Fizz):
        return 'fizz'
    elif isinstance(fblist, Buzz):
        return 'buzz'
    elif isinstance(fblist, FizzBuzz):
        return match_fizzbuzz(fblist.fizz) + match_fizzbuzz(fblist.buzz)
    elif isinstance(fblist, Cons):
        return '{}, {}'.format(
                match_fizzbuzz(fblist.car),
                match_fizzbuzz(fblist.cdr))
    elif isinstance(fblist, Nil):
        return None

とはいえ、if 文を使うことでその順序に依存関係ができてしまうため、データ型が派生して複雑になったとき (例えば、FizzBuzz 型が Fizz 型と Buzz 型を継承するといったとき) に型のマッチングという厳密性が有効になる気がします。

Python は代数的データ型 (直和型) を言語としてサポートしていないため、

• 型を組み合わせて新たな型を定義する
• データをトラバースしながら処理する

といった考え方を普通にはしないような気がするので、試してみて考え方の違いを実感できておもしろかったです。

あともう1点、Fizz Buzz のロジックがデータの生成時に出てきました。データの生成方法を変えることで出力側 (パターンマッチのところ) を変えなくても、出力結果を変更できるというのも違うというのに気付きました。