Edited at

代数的データ型と FizzBuzz と

More than 3 years have passed since last update.

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

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)

ListNilCons から成るというのを表現するとこんな感じです。

空のリストは、


3.4

>>> Nil()

Nil()

要素をもつリストは、


3.4

>>> Cons(1, Cons(2, Nil()))

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

Cons.cdrCons を渡すことで表現できます。要素がないときは 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)


FizzBuzzListList の特性を受け継ぎ、ValueFizzBuzzFizzBuzz から成ると定義します。先ほどと同様に 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 を継承した 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 のロジックがデータの生成時に出てきました。データの生成方法を変えることで出力側 (パターンマッチのところ) を変えなくても、出力結果を変更できるというのも違うというのに気付きました。