Help us understand the problem. What is going on with this article?

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

t2y
I like programming!
https://t2y.hatenablog.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした