Python の空リストと再帰

2008年10月11日土曜日

Python の空リストと再帰

「Python でリスト内のリストを連結」において、冗長な再帰関数の書き方をしてしまった。(+_+) 今回はなぜこのような書き方をしたのか考えてみることに。

冗長な再帰関数

まずは、冗長な再帰関数の例。例えば、与えられた数値のリストの各要素を 2 倍にする関数 rec_ があるとする。

def rec_(L):
    if L == []:
        # リストが空の場合
        return []
    elif len(L) == 1:
        # リストの要素が一つの場合
        return [L[0] * 2]
    else:
        # リストの要素が二つ以上ある場合
        return rec_([L[0]]) + rec_(L[1:])

とりあえず動くのだけれど… ^^;

上記を見るとわかるように、リストの要素数に応じて 3 つの場合に分けて考えている。

空
要素が一つ
要素が二つ以上

なぜこのような方法を考えたかと言うと、再帰を考えるとき、ベースとなる空のリストが渡される場合から、徐々に要素が増えていく場合をイメージしたため。次ように、

空のリストが渡されたら → [ ] を返す。
要素が一つだけのリストが渡されたら → 要素を 2 倍にして、リストに戻して返す。
要素が二つ以上あった場合、
- 先頭の要素を取り出して、「要素が一つだけの場合」の処理がされるように再帰的な呼出しをする。
- 先頭以外の要素は、何もせずに再帰的な呼出しをする。
- 上記二つの結果をリストにするために結合する。

何が冗長かと言えば、

要素が一つのとき、 len(L) == 1 の条件の中の文しか実行されないこと。つまり、最後の再帰的な呼出しが全く利用されていない。何かもったいない感じが。 ^^;
要素が二つ以上のとき、L == [] の条件の中の文が実行されない。

空リスト

上記のコードを次のように書換えると、コードがまんべんなく利用される。

def rec(L):
    if L == []: return []
    else:
        return [L[0]*2] + rec(L[1:])

これを理解する前に、次のコードを実行。

    print [1]
    print [1] + []
    print [1] + [] + []

    print [1][0]
    print [1][1:]

結果は、

[1]
[1]
[1]
1
[]

次のことがわかる。

リストに「空のリスト」を足してもリストは変わらない。
要素一つのリストに対して、 2番目以降の要素を取得しようとすると「空のリスト」が返される。

これを踏まえた上で、上記のコードを見ると、例えば引数に [1] が渡されたら、

return [L[0]*2] + rec(L[1:])

の部分は、次のように計算が進められる。

return [1*2] + rec([])
return [2] + []
return [2]

要素が二つの場合では、例えば引数に [1,2] が渡されると、

return [1*2] + rec([2])
return [2] + ([2*2] + rec([]))
return [2] + ([4] + [])
return [2] + [4]
return [2,4]

「空のリスト」が再帰の終着点になっていることがわかる。つまり、リストは、最後の要素の後ろに「空のリスト」があるとイメージしておくと、再帰のコードが書きやすくなる。

2.3.6 シーケンス型によると、

s[i:j] s の i 番目から j 番目までのスライス …

j が省略された場合、len(s) を使います。 i が j 以上の場合、スライスは空のシーケンスになります。

実際にどうなっているのかわからなかったけれど、概念的なイメージとしては以下のように考えておくことにした。

Haskell のリスト

ところで、Haskell においては明確にリストの末尾が「空リスト」であることが定められているようだ。

ふつうのHaskellプログラミングによると、

… 空リスト (empty list) は特別な値で、リストの末尾に現われます (p36)

Haskell/Lists and tuples - Wikibooks, collection of open-content textbooks には、普通にリストを書く書き方は、リストのデータコンストラクタ (:) の syntactic sugar であることが述べられている。

The commas and brackets notation is actually a pleasant form or syntactic sugar. In other words, a list like [1,2,3,4,5] is exactly equivalent to 1:2:3:4:5:[]

空のリストが末尾に結合している。

また、The Haskell 98 Report: Standard Prelude を見ると、

data [a] = [] | a : [a] deriving (Eq, Ord) -- Not legal Haskell; for illustration only

末尾が [] となることがわかる。

多分、 Python も同じような感じだと思うのだけれど、どうなんだろう (?_?)

7.3.5 List Objects には、

PyObject* PyList_GetSlice(PyObject *list, int low, int high)

戻り値: 新たな参照.

list 内の、low から high の間のオブジェクトからなるリストを返します。失敗すると NULL を返し、例外をセットします。 list[low:high] に類似した機能です。

とあるが、NULL ? 例外？うーーーん (@_@;)

その他

代数的データ型 – Wikipediaには、

例として、Haskell言語でのリスト型を示す:
data List a = Nil | Cons a (List a)
これは、リスト a は空のリストの場合と 'a' を先頭に持つリストの場合があることを示している。

Recursive type - Wikipedia, the free encyclopedia には Java による non-empty list の例がある。Haskell では、Non-empty list – HaskellWiki 。

すぐに忘れる脳みそのためのメモ

2008年10月11日土曜日