LoginSignup
24
20

More than 5 years have passed since last update.

@t2y

代数的データ型とパターンマッチングと

Last updated at Posted at 2015-03-03

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

動機付け

代数的データ型 について、私の知りたかったことが ADTs for Python に書かれているように思います。とはいえ、当初 wikipedia (日本語) の説明を読んでもよく分からなくて、いくつかのブログやコードを読んで理解度を上げてから読んだため、最初にくだんのブログ記事を読んでも理解度が足らなかったかもしれないというのも否定はできません。

代数的データ型について、日本語で入門的な分かりやすいものを私は見つけられていなかったのですが、以下の説明が端的に表していて受け入れやすいように私は思いました。

豊かなデータ型を持つ
一般的に関数型言語は，構造体（直積），共用体（直和），列挙型および再帰型を統合し，簡潔に表現できる豊かなデータ型を提供しています。この豊かなデータ型を使えば，たとえば木構造を簡潔に，しかも（危険なnullを使わないで）安全に定義できます。もちろんこの木構造は永続データです。

また，豊かなデータ型と表裏一体の機能であるパターンマッチングによって，データを直感的に操作できます。型が豊かであればあるほど，問題を容易に，しかも安全に解けるようになるので，プログラミングが楽しくなります。

「プログラミングが楽しくなります」 というのがいい響きだなと思いました。

Python における代数的データ型

Python は関数型プログラミング言語ではなく、代数的データ型もサポートしていません。

昨夏に mypy の型アノテーションの構文を Python 3.5 に取り入れると提案があったときに Python の型システムについての議論が活発になりました。Andrew Barnert 氏による ADTs for Python もそのときに書かれた記事の1つです。基本的には、この記事を読み進めながら自分で理解するために考察してみます。

一通り読んだことのまとめとして書いていますが、私の理解・解釈が誤っているところもあると思うのでおかしいところがあったらツッコミ歓迎です。

直積型 (Product types)

多くのプログラミング言語では、構造体や (オブジェクト指向プログラミングで言うところの) オブジェクトとして直積型を表現します。

Note the equivalency to the "implicit namedtuple literals" that people suggest for Python every few months.

Python では namedtuple がリテラルとしての直積型に相当するとあります。

3.4
>>> from collections import namedtuple
>>> Stuff = namedtuple('Stuff', ['answer', 'manna'])
>>> type(Stuff)
<class 'type'>
>>> s = Stuff(42, 'spam')
>>> s
Stuff(answer=42, manna='spam')
>>> s.secret = 'cannot assign'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'Stuff' object has no attribute 'secret'

また namedtuple の代替として __ slots __ を使うのも名前付きレコード型 (named record type) に近いものだと補足されています。

3.4
>>> class StuffSlots:
...     __slots__ = ('answer', 'manna')
...     def __init__(self, answer, manna):
...         self.answer = answer
...         self.manna = manna
... 
>>> s2 = StuffSlots(52, 'ham')
>>> s2.answer
52
>>> s2.manna
'ham'
>>> s2.secret = 'cannot assign'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'StuffSlots' object has no attribute 'secret'

但し、タプルではないということが、実用上は良くても理論上の問題を抱えてしまうともあります。その理由として、コンストラクタの引数を slots に対応付けを強制するものがなく、匿名的にインライン展開でコーディングする方法を想像しにくいからだと述べられています。

試しに前述した StuffSlots を type クラスのコンストラクタで表現してみましょう。

3.4
>>> StuffSlotsType = type('StuffSlotsType', (object,), dict(__slots__=('answer', 'manna'), __init__=lambda self, answer, manna: setattr(self, 'answer', answer) or setattr(self, 'manna', manna)))
>>> s3 = StuffSlotsType(62, 'egg')
>>> s3.answer
62
>>> s3.manna
'egg'
>>> s3.secret = 'cannot assign'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'StuffSlotsType' object has no attribute 'secret'
>>> s3.__slots__
('answer', 'manna')
>>> s3.__dict__
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'StuffSlotsType' object has no attribute '__dict__'

__slots__ と __init__ を正しく定義しないといけないのが煩雑だ、ということかなぁ。

直和型 (Sum types)

これを簡潔に表現できるのが関数型プログラミング言語の特徴の1つに言われているように思います。

Python doesn't have sum types at all, except implicitly.

この「暗黙的なものを除いて」がどういったものを指しているのか私には分かりませんが、Python には直和型に相当するものがありません。

And explicit sum types, especially either tagged sums of anonymous products or sums of named products, are exactly what people are missing when they ask for ADTs in Python.

「明示的な」直和型として、匿名の直積型の和、または名前付き直積型の和を考えるときに Python に欠けている代数的データ型に辿り着くようです。

ここで言う「明示的な」というのは既存の Python の型システムでどう実装するかということを指しているように思います。2つのアプローチからその実現方法を考察しています。

MyPy Union

Haskell のような Maybe の定義を紹介しています。元記事では、型変数の T を使ったり、Union の代わりに | (パイプ) を使って表現しています。

While this only gives us untagged unions, as noted above, tagged unions are equivalent to untagged unions of record types. So, if we wanted to define a Haskell-like Maybe, we could do this:

    Just = namedtuple('Just', (('value', T,)))
    Nothing = namedtuple('Nothing', ())
    Maybe = Just | Nothing

Also, without pattern matching, the only way to actually use this is with isinstance checks (or EAFP try/except):

    def spam(eggs: Maybe[int]):
        if isinstance(n, Just[int]):
            print('Spam with {} eggs'.format(eggs.value))
        else:
            print('The spam stands alone')

これが疑似コードだと明に書いていませんが、このコードは Python (mypy) では実行できません。

そこで実際に実行可能な Python のコードで表現すると以下のようになります。

mypy_sum1.py
# -*- coding: utf-8 -*-
from typing import typevar, Generic, Union

T = typevar('T')

class Just(Generic[T]):

    __slots__ = ('value',)

    def __init__(self, value: T) -> None:
        self.value = value

class Nothing:
    """
    mypy claims by defining Nothing as below

    >>> Nothing = namedtuple('Nothing', ())
    List literal expected as the second argument to namedtuple()

    >>> Nothing = type('Nothing', (), dict(__slots__=()))
    Invalid type "__main__.Nothing"
    """
    __slots__ = ()

Maybe = Union[Just, Nothing]

def spam(eggs: Maybe):
    if isinstance(eggs, Just[int]):
        eggs.value += '+1'
        print('Spam with {} eggs[int].'.format(eggs.value))
    elif isinstance(eggs, Just[str]):
        eggs.value += 1
        print('Spam with {} eggs[str].'.format(eggs.value))
    else:
        print('The spam stands alone')

mypy の namedtuple の型チェックの扱いがよく分からない動作をするため、ここでは __slots__ を使って直積型 (Just と Nothing) の代替となるものを定義しています (mypy の型チェッカーのエラーを回避するため) 。

mypy の構文としては以下のように直和型を定義します。

3.4
Maybe = Union[Just, Nothing]

では、型チェッカーを実行してみましょう。

(mypy)$ mypy sum_mypy1.py 
sum_mypy1.py: In function "spam":
sum_mypy1.py, line 29: Unsupported operand types for + ("int" and "str")
sum_mypy1.py, line 32: Unsupported operand types for + ("str" and "int")

行番号を記載していないので分かりにくいですが、spam() 関数の意図した eggs.value += ... の箇所で型エラーを捕捉できました。

この spam() 関数の isinstance による実装について、

There's nothing theoretically wrong here, but it certainly is ugly.

理論的には間違っていないけれど、これは格好悪いねと Andrew 氏は言っています :cry:

ここから先は余談ですが、このコードは mypy 的には正しい構文ではあるものの、Python 的には誤ったコードです。

3.4
>>> from sum_mypy1 import *
>>> spam(Just[int](3))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File ".../sum_mypy1.py", line 29, in spam
    eggs.value += '+1'
TypeError: unsupported operand type(s) for +=: 'int' and 'str'

int 型の値をコンストラクタに取るときは型チェッカーと同様に型エラーとなりますが、

3.4
>>> spam(Just[str]('ham'))
Spam with ham+1 eggs[int].

str 型の値をコンストラクタに取るときは実行できてしまいます。

Just[T] は mypy の構文での表現であり、Python のコードとしては isinstance(eggs, Just[T]) は isinstance(eggs, Just) でしかないからです。そのため、spam() 関数の Just[int] を想定した方のコードが実行されます。

mypy の構文は、既存の Python コードの実行に影響を及ぼさないように実装されているため、この辺りが mypy と Python の動的型付けとの境界とも言えるかもしれません。

Swift-style Enum

もう1つの直和型を表現する方法として、Swift スタイルの enum 型を紹介しています。

Python の enum モジュールでは、以下のようなコードは動きませんが、この疑似コードの意図は分かりやすいかと思います。

3.4
class Barcode(Enum):
    UPCA: (int, int, int, int) = 1
    QRCode: str = 2

enum 定数のコンストラクタに渡される引数がそれぞれ名前を持つパターンです。

3.4
class Barcode(Enum):
    UPCA: (LL: int, L: int, R: int, RR: int) = 1
    QRCode: str = 2

再帰型

代数的データ型の重要な機能の1つは再帰的に扱えることだとあります。

以下のようにリストを代数的データ型で表現した場合、

List(Cons(head: T, tail: List[T]) | Nil())

List 型は Cons 型と Nil 型から成り、Nil() は Nil 型と List 型のインスタンスであり、Cons(1, Nil()) は Cons[int] 型と List[int] 型のインスタンスでもある。

このとき Cons (のコンストラクタ) から List 型を (名前) 解決できる必要があります。

Python の場合、mypy で実現しているような 前方参照 (forward reference) か、その型が定義されているかのように扱える直和型やレコード型を定義しなければいけないと述べられています。

代数的データ型とは単にクラスのサブセットなのか？

namedtuple や enum の実体は Python だとクラスです。そして Python では全ての型がクラスです。

More importantly, ADTs are a strict subset of classes. The "strict subset" part is what makes them useful: they have a static structure, they have

重要なのは、代数的データ型はクラスの "厳格なサブセット (strict subset)" であるということです。この 厳格なサブセット の何が便利かというと静的な構造をもつから ... ？

ごめんなさい、ここの英文の訳と意図が私には分かりません。誰か教えてください。 :cry:

本当に代数的データ型は Python に必要なのか？

クラスの代わりに namedtuple や enum で実装した代数的データ型を使いたいかどうかという大きな疑問があります。

If the language had pattern matching that only worked on ADTs, the answer might well be "quite often".

もし言語が代数的データ型のみを扱うパターンマッチングをもっているとしたら、その答えは "quite often" と言ってもいいでしょう。

But without pattern matching, or with pattern matching that worked on classes that chose to opt in (as described in my previous blog post), I think it wouldn't be that often.

しかし、パターンマッチングがない、もしくはオプトインを選択したクラス上で動作するパターンマッチングの場合は "often" とは言えないだろうと Andrew 氏は考えています。

元記事では代数的データ型とパターンマッチングのパラダイムを説明するのに JSON をパースする ML or Haskel 風のパターンマッチングを模した疑似コードが紹介されています。

class Name((first: str, last: str)):
    def tojson(self):
        return JSON.object({'first': self.first, 'last': self.last})

    @classmethod
    def fromjson(cls, j):
        case j:
            of JSON.object as o:
                return cls(o['first'], o['last'])
        raise ValueError('{} is not a name'.format(j))

class Person((aliases: Sequence[Name], age: float)):
    def tojson(self):
        return JSON.object({'aliases': JSON.array(map(Name.tojson, self.aliases)), 'age': age})

    @classmethod
    def fromjson(cls, j):
        case j:
            of JSON.object as o:
                case o['aliases']:
                    of JSON.array as a:
                        return cls([Name.fromjson(name) for name in a], o['age'])
        raise ValueError('{} is not a person'.format(j))

パターンマッチングがない場合、こういった木構造をトラバースする処理を Visitor パターン で実装するのが一般的 (？) なのかもしれません。

冒頭で紹介した関数プログラミングの入門記事における

豊かなデータ型と表裏一体の機能であるパターンマッチングによって，データを直感的に操作できます。

の一文の意図していることを伺えます。

まとめ

関数プログラミングの代数的データ型は、パターンマッチングと一緒にその概念を学ぶと、その表現力の簡潔さと有効性が分かりやすいと思います。

So, is that a good enough use case to include ADTs in Python?

24
20
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
Sign upLogin
24
20