読者です 読者をやめる 読者になる 読者になる

ゆくゆくは有へと

おかゆ/オカ∃/大鹿有生/彼ノ∅有生 の雑記

python でリストのパターンマッチっぽい何か

python

「実践Python3」のコラム見て、ハッと閃いたのでメモ。(Python3.5)

シーケンスのアンパックは引数定義のところでよく使われますね。

def func(*args, **keywords):
  pass

みたいな感じで。アンパックはまだ使いみちがあって、入れ子になったシーケンスの内側にあるシーケンスをアンパックして平たくできます。

[1, 2, 3, *[4, 5, 6]]
# >> [1, 2, 3, 4, 5, 6]

ところで、Pythonではアンパック代入というのができて、・・・要はタプルの内部に変数を置けます(パターンマッチ的な代入?なんて言うのか分からない)

tpl = (1, 2, 3)
a, b, c = tpl # (a, b, c) = tpl に同じ
assert a == 1 and b == 2 and c == 3

で、このアンパック代入、対タプルならイミュータブルなので割と使えますが、ミュータブルなシーケンス(リストとか)だとふつうの使い方では使い勝手が悪い。

ここで*の出番です。

seq = [1, 2, 3, 4, 5]
x, *xs = seq
assert x == 1
assert xs == [2, 3, 4, 5]

アンパック代入時、最後に*を付した変数を入れておけば、余った部分は全部そこに収容されるので、多い日もあんしん!((少ないときはifして))

で、これ使うと Haskell みたいなリストの取り扱い方(x:xsみたいなの)ができそうだと思って、「すごいH本」4章の実装練習を Python でやってみました。

from typing import List, TypeVar, Tuple, Sequence, Any
from abc import ABCMeta, abstractmethod

T = TypeVar('T')
S = TypeVar('S')
CT = TypeVar('CT', bound=Comparable)

class Comparable(metaclass=ABCMeta):
    @abstractmethod
    def __lt__(self, other: Any) -> bool: pass
    @abstractmethod
    def __gt__(self, other: Any) -> bool: pass
    def __le__(self, other: Any) -> bool:
        return not self > other
    def __ge__(self, other: Any) -> bool:
        return not self < other

def sum_(xs: Sequence[float]) -> float:
    if xs:
        x, *xs = xs
        return x + sum(xs)
    else:
        return 0

def maximum_(xs: Sequence[T]) -> T:
    if xs:
        x, *xs = xs
        if xs:
            return max(x, maximum_(xs))
        else:
            return x
    else:
        raise ValueError("maximum of empty list!")

def take_(n: int, xs: Sequence[T]) -> List[T]:
    if n >= 0 and xs:
        x, *xs = xs
        return [x] + take_(n-1, xs)
    else:
        return []

def reverse_(xs: Sequence[T]) -> List[T]:
    if xs:
        x, *xs = xs
        return reverse_(xs) + [x]
    else:
        return []

def zip_(xs: Sequence[S], ys: Sequence[T]) -> List[Tuple[S, T]]:
    if xs and ys:
        x, *xs = xs
        y, *ys = ys
        return [(x, y)] + zip_(xs, ys)
    else:
        return []

def elem_(a: T, xs: List[T]) -> bool:
    if xs:
        x, *xs = xs
        if a == x:
            return True
        else:
            return elem_(a, xs)
    else:
        return False

def quicksort_(xs: List[CT]) -> List[CT]:
    if xs:
        x, *xs = xs
        smaller_or_equal = [a for a in xs if a <= x]
        larger = [a for a in xs if a > x]
        return quicksort_(smaller_or_equal) + [x] + quicksort_(larger)
    else:
        return []

という感じで。え? pop使えって?うるせーニシキヘビぶつけんぞ。とはいえ確かにジェネレータとかに対しては不向き(特に無限イテレータ)ですね。

とはいえ、ジェネレータで実装する場合はそもそも上のような書き方をしないのでは、とも思うので、もっぱらリスト向きの(トイな)書き方ではある。

ジェネレータで再帰するならyield fromを使うとよさそう

from typing import Iterable, Iterator

def reverse_2(xs: Iterable[T]) -> Iterator[T]:
    xs = iter(xs)
    x = next(xs)
    yield from reverse_2(xs)
    yield x

assert list(reverse_2(range(5))) == [4, 3, 2, 1, 0]

一周してジェネレータを積極的に使いたみというオチになってしまった。ちなみに、遅延評価の Haskell なら簡単にかけるrepeatPython ではジェネレータで書けます。

def repeat(x: T) -> Iterator[T]:
    yield x
    yield from repeat(x)

ジェネレータ便利やね。(全く同じ形式で、yield from repeat(x+1) とすればカウンターになるのも面白い)

ジェネレータ、ループにはwhile使うのが常套手段っぽいけど、再帰のほうがなんかかっこよくていいですよね(?)

P.S.

ところで、Comparable の抽象基底クラスってなんでないんやろ