代数的データ型と FizzBuzz と

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

[PyAlgebraicDataTypes]
(https://github.com/benanhalt/PyAlgebraicDataTypes) を使って遊んでみました。[Racket](http://racket-lang.org/) という言語に触発されて [代数的データ型](http://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B) を Python で表現するといったライブラリのようです。学習向けに小さくて良さそうだったので試してみました。

```py3: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* から成るというのを表現するとこんな感じです。
空のリストは、

```py3:3.4
>>> Nil()
Nil()
```

要素をもつリストは、

```py3:3.4
>>> Cons(1, Cons(2, Nil()))
Cons(car=1, cdr=Cons(car=2, cdr=Nil()))
```

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

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

```py3: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](http://ja.wikipedia.org/wiki/Fizz_Buzz) 的なデータ構造をもつ *FizzBuzzList* を定義してみます。

```py3: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* も作ってみましょう。

```py3: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 を出力してみます。

```py3: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
```

こんな感じ。

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

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

```py3: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 のロジックがデータの生成時に出てきました。データの生成方法を変えることで出力側 (パターンマッチのところ) を変えなくても、出力結果を変更できるというのも違うというのに気付きました。