2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

代数的データ型と FizzBuzz と

Last updated at Posted at 2015-02-27

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

[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)

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

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?