Pythonのiterable

#  iterable

### イテラブルオブジェクト

イテラブルオブジェクトとはfor文で反復可能なオブジェクトのことです.

```Python 
# range(5) - range()関数の返すオブジェクトはイテラブル
 for i in range(5) :
    print(i)
    
# [1,2,3]　- リストはイテラブル
for i in [1,2,3] :
    print(i)

# "apple" - 文字列も イテラブル
for i in "apple" :
    print(i)

# 他にも, 辞書, セット,　タプルなどもイテラブル
```
### イテレーター

イテレーターはオブジェクトが無限に連なっている鎖のようなイメージの構造をもつオブジェクトです.　イテレーターはリストに似ていますが少し違います. イテレーターとリストの違いをこの記事では少しずつ明確にします. イテレーターもfor文で反復可能なのでイテラブルオブジェクトの一種です. 

 `オブジェクト1` - `オブジェクト2` - `オブジェクト3`　- ... - `オブジェクトn` - ...

> 数学の言葉でいうとイテレーターは点列 $\lbrace a_n  \rbrace_{ n=1,2,...}$
です. 　点列の点が数のとき,それを数列といいます. 数列には無限数列と有限数列があります. 数列は以下のような自然数の集合を定義域にもつ写像(関数)のことです.
無限数列:　$a:N→\mathbb R; n\mapsto a_n$　
有限数列:　$a:\{\lbrace	1,2,...,n  \rbrace}\rightarrow \mathbb R  $
文字列を表す点列:$\{\lbrace	1,2,...,n  \rbrace}\rightarrow \mathcal S$   （$\mathcal S$は文字の集合）
型のある言語だとイテレーターと点列の概念は対応します. 

イテレーターにも鎖の構造が無限のものと有限のものがあります. 
無限 : `オブジェクト1` - `オブジェクト2` - `オブジェクト3`　- ... - `オブジェクトn` - ...
有限 : `オブジェクト1` - `オブジェクト2` - `オブジェクト3`　- ... - `オブジェクトn`

```Python
# 無限のイテレーターの例
import itertools

cycler = itertools.cycle("ABCD")
for i, val in enumerate(cycler):
    print(i, val)

# 0 A
# 1 B
# 2 C
# 3 D
# 4 A
# 5 B
# 6 C
# 7 D
# 8 A
# ... と永遠に続く
```

:::note warn
リストと有限のイテレーターの違い ~その1~ 

有限のイテレーターはリストと全く同じように感じます. 
- もっともわかりやすい違いはリストが要素に何度でもアクセスできるのに対し, イテレータは消費され,1度のみしか呼び出されない点です. 詳しくは「`for`文
イテレーターでできている」の項で説明します.
- 重要な違いはリストが具体的なデータ構造で全要素をメモリに保持するのに対し, イテレータは必要に応じて要素を生成し,呼び出されたら要素を捨てる点です. 詳しくは遅延評価の項で説明します.
:::


##### `iter`関数

イテレーターを作る最も簡単な方法が`iter()`関数を用いることです.　`iter()`関数はイテラブルなオブジェクト,たとえばリストやrange()オブジェクトなどに対してイテレーター(鎖の構造)を返す関数です.
`iter()`関数　｜【入力】 `イテラブルなオブジェクト`　【出力】 `イテレーター`

```Python
r=iter(range(4)) 
l=iter(["Alice","Bob","Camelon"])
s=iter("aiueo")

# イテレーターはイテラブルオブジェクトなのでfor文がつかえる
for i in r :
    print(i)

for i in range(4) : 
    print(i)
# 上の2つのコードは出力は等しい
    
```
この時点だと,イテレーターにする意味もわからないし,リストとの違いもわかりません.


##### `next`関数

`next()`関数は連なっている鎖を先頭の鎖(オブジェクト)を外して吐き出す関数です. 吐き出されたオブジェクトはイテレーターから破棄されて同じイテレーターからは二度と`next()`関数では呼び出せません.

`イテレーターA` : `オブジェクト1` - `オブジェクト2` - `オブジェクト3`　- ... - `オブジェクトn` - ...

というイテレーターに対して`next(イテレーターA)`とすると,先頭の鎖`オブジェクト1`を返して, `イテレーターA`の先頭の鎖`オブジェクト1`は切り離され, 

`イテレーターA` :`オブジェクト2` - `オブジェクト3`　- ... - `オブジェクトn` - ...

という構造になります.
```Python
l=iter(["Alice","Bob","Camelon"])   

print(next(l)) # 鎖l: "Alice"-"Bob"-"Camelon"
# Alice
print(next(l)) # 鎖l: "Bob"-"Camelon"
# Bob
print(next(l)) # 鎖l: "Camelon"
# Camelon 
print(next(l)) # 鎖l: 空
# Stop Iteration Errorとなる. 
```
有限のイテレーターの場合, 鎖がすべて吐き出されると空になります. 空っぽになったイテレーターに`next()`関数を使うと, `Stop Iteration Error`となります.

:::note warn
イテレーターとイテラブルオブジェクトの違い ~その$2$~

range(5), リスト, 文字列はイテラブルオブジェクトであるが,イテレーターではないので,`next()`関数を使うことができない.

:::

たとえば,リストに対して`next()`関数を適用しようとすると,「リストはイテレーターでない」と怒られてしまいます.

```Python
l=["Alice","Bob","Camelon"]
next(l) 
# TypeError: 'list' object is not an iterator
```

ここまでの解説だとまだ全然イテレーターのありがたみがわかりません.リストをpopするのとイテレーターをnextするのと動作的には同じであると思ってしまうかもしれません. イテレーターはクラスと組み合わせたり,ジェネレーターを使ったときに威力を発揮します. あとでその例を出します.

### `for`文はイテレーターでできている

Pythonのfor文は
1. イテラブルから`iter()`関数でイテレーターを作成する
2. 作成したイテレーターに対して無限ループで`next()`関数を繰り返し呼び出す
3. `Stop Iteration Error`を受け取ったらループを抜ける
という仕組みで動いています

次のコードがどのように動いているかというと
```Python
for i in ["Alice","Bob","Camelon"] :
    print(i) # iに関する処理部分
```
イテラブルオブジェクト`["Alice","Bob","Camelon"]`を受け取ったらそれを`iter`関数でイテレーターに変えて, `i=next()`をループでくり返し行なう. イテレーターの中身がなくなり,  `Stop Iteration Error`を受け取ったらループを抜けるということです. 次のコードと等価です.

```Python
iterable=iter(["Alice","Bob","Camelon"]) 
while True :
    try :
        i=next(iterable)
        print(i) # iに関する処理部分
    except StopIteration:
        break # iterableが空になったらループからぬける
```

よって,次のようにイテレーターに使うと`StopIteration`エラーとなります. しかし, リストの場合はエラーになりません. 

```Python
l=["Alice","Bob","Camelon"] # リスト
il=iter(l) # イテレーター

# リストをイテレーターに変えてそのイテレーターに対して反復するからもとのリストは影響うけない
for i in l : 
    print(i)
for i in l :
    print(i)
# エラーならない

for i in il : 
    print(i)
# この時点ilは空のイテレーターとなる
for i in il :
    print(i)
# 空のイテレーターに対してnext()関数を適用しようとしているからStop Iteration Errorになる. 
```
:::note warn

イテレーターとイテラブルオブジェクトの違い ~その $3$ ~

 イテラブルであるには `for`文の定義をみればわかる通り `　iter()`関数でイテレーターが作成可能でないといけません. しかし, イテレーターは`iter()`関数によりイテラブルオブジェクトから作成しています.  

現状だとイテラブルオブジェクトとイテレーターの関係は「にわとりと卵の関係」です. 次の項でクラスによって,独自のイテラブルオブジェクトを定義する方法を紹介します. 
:::

### クラスでイテラブルなオブジェクトを定義する

クラスの特殊メソッド`__iter__`,`__next__`を用いて独自のイテレーターを作成することができます. これらの機能を用いてフィボナッチ数列のクラスとアルファベットのクラスを実装する例を挙げます.

あるクラスから生成されたオブジェクトoに対して
- `iter(o)`はoの特殊メソッド`__iter__`を実行する.
- `next(o)`はoの特殊メソッド`__next__`を実行する.

要は`iter(o)`は`o.__iter__()`と等価で`next(o)`は`o.__next__()`ということです. 

##### `Fibonacci()`イテレーターのクラスの作成

フィボナッチ数列$\{\lbrace	a_n  \rbrace}_{n=1,2,...}$のイテレーターを生成するクラスをつくります. フィボナッチ数列とは

$a_{n+2}=a_{n+1}+a_{n}, \ n=0,1,2,...$

を満たす3項間漸化式で定義される無限数列です. これを無限のイテレーターで表すことができます. 漸化式の初期条件$a_0,a_1$を与えたときに, フィボナッチ数列に対応する無限のイテレーターを返してくれるクラスを実装します.

$a_0=1,a_1=1$
を渡したとき生成されるイテレーターの鎖のイメージは
$1-1-2-3-5-8-13-21-34-...$
という無限の鎖のイメージです.

``` Python
class Fibonacci:
    def __init__(self, first=1, second=1):
        self.a, self.b = first, second  # 初期条件の2つの数を引数から設定

    def __iter__(self):
        return self

    def __next__(self):
        current = self.a
        self.a, self.b = self.b, self.a + self.b
        return current

fib=Fibonacchi(1,1)
next(fib)
# 1
next(fib)
# 1
next(fib)
# 2
next(fib)
# 3

# 50以下のフィボナッチ数をプリント
for i in Fibonacchi(1,1) :
    print(i)  
    if i<50 : break

print(list(fib)) #永遠にプリントできない
        
```

イテレーターの一度, 消費された値が破棄されるという構造上, 


``` Python
fib=Fibonacchi(1,1)
next(fib)
# 1
next(fib)
# 1
next(fib)
# 2
next(fib)
# 3

# とした後に
for i in fib :
    print(i) 
# 5,8,13, ...となる
```

となってしまったり

``` Python
fib=Fibonacchi(1,1)

for i in fib :
    print(i) 
    if i<50 : break

for i in fib :
    print(i) 
    if i<10 : break
# 1 1 2 3 5 8とプリントされてほしいが,
# 既にこの値をイテレーターが吐き出してしまっているためプリントされない
```
となってしまうという問題点があります.この問題を解決したいです.


##### `Fibonacci()`クラスの作成

先の項での問題を解決するには, `Fibonacci()`クラスとは別の`FibonacciIterator()`イテレータのクラスを別に定義して、そのクラスから作成されるオブジェクト`Fibonacci()`クラスの`__iter__`メソッドから返すようにすればよいです. さっぱり, わからない方は実装を見た方がよいかもしれません. 

`Fibonacci()`クラスは単にイテラブルなオブジェクトを返すクラスとして機能して, イテレーションのロジックは`FibonacciIterator()`クラスに委ねるということです.

``` Python
class Fibonacci:
    def __init__(self, first=0, second=1):
        self.first = first
        self.second = second

    def __iter__(self):
        return FibonacciIterator(self.first, self.second)

class FibonacciIterator:
    def __init__(self, first, second):
        self.a, self.b = first, second

    def __iter__(self):
        return self

    def __next__(self):
        current = self.a
        self.a, self.b = self.b, self.a + self.b
        return current        

fib=Fibonacchi(1,1)

for i in fib :
    print(i) 
    if i<10 : break

for i in fib :
    print(i) 
    if i<10 : break

next(fib)
# TypeError: 'Fibonacci' object is not an iterator

```

このように実装するとfor文を回すたびに`fib`というイテラブルオブジェクトから`iter()`関数でイテレーターを作成されて作成されたイテレーターを使ってfor文を回すから, このような書き方ができます. このプログラムをみてはじめて, イテレーターとイテラブルオブジェクトと違いがわかります.

:::note warn

イテレーターとイテラブルオブジェクトの違い　~その$4$~

イテレーターとイテラブルオブジェクトの本当の定義は

- イテラブルオブジェクトとは`__iter__`関数が実装されているクラスから生まれたオブジェクト
- イテレーターとは`__iter__`関数と`__next__`関数が実装されているクラスから生まれたオブジェクト

:::

この定義によると`Fibonachi()`クラスから生成されるオブジェクトはイテラブルオブジェクトですがイテレーターではありません. `FibonachiIterator()`クラスから生成されるオブジェクトはイテレーターです. 

##### `Alphabet()`イテレーターのクラスの作成


``` Python
class Alphabet:
    def __init__(self, start, end):
        self.start = ord(start)  # 開始文字のUnicodeコードポイント
        self.end = ord(end)  # 終了文字のUnicodeコードポイント
        self.current = self.start - 1  # 現在位置を開始文字のひとつ前に設定

    def __iter__(self):
        return self

    def __next__(self):
        if self.current < self.end:
            self.current += 1  # 現在位置を次の文字に更新
            return chr(self.current)  # 現在位置の文字を返す
        else:
            raise StopIteration  # 終了文字を超えたらイテレーションを終了

# 使用例
for char in Alphabet('a', 'e'):
    print(char,end+"")
# abcde

``` 

フィボナッチ数列と違い, 有限の長さをもつイテレーターです. 

### 組み込み関数`range()`,`zip()`,`enumrate()`を書いてみる

イテラブルオブジェクトについて理解するため,Pythonに組み込まれいる`range()`クラスと`zip()`クラス,`enumrate()`クラスを理解するために, これらと同じような挙動をもつクラスを実装しましょう.

##### `range()`クラス

`range()`クラスから作成される`range()`オブジェクトはイテラブルオブジェクトです. `range()`クラスと似たふるまいをする`MyRange()`クラスを実装します.

``` Python
class MyRange:
    def __init__(self, start, stop=None, step=1):
        if stop is None:
            self.start = 0
            self.stop = start
        else:
            self.start = start
            self.stop = stop
        self.step = step

    def __iter__(self):
        return MyRangeIterator(self.start, self.stop, self.step)

class MyRangeIterator:
    def __init__(self, start, stop, step):
        self.current = start
        self.stop = stop
        self.step = step

    def __iter__(self):
        return self

    def __next__(self):
        if (self.step > 0 and self.current >= self.stop) or (self.step < 0 and self.current <= self.stop):
            raise StopIteration
        else:
            current = self.current
            self.current += self.step
            return current

# MyRangeの使用例
next(MyRange(3)) 
# TypeError MyRange()クラスの生成するオブジェクトそのものはイテレーターではない

for num in MyRange(5, 1, -1):
    print(num, end=" ")
# 5 4 3 2

list(MyRange(3))
# [0,1,2]
```

##### `enumrate()`クラス

`enumerate()`はイテラブルなオブジェクトを受け取って, 受け取ったイテラブルオブジェクトの中身と番号をペアにしたタプルを(番号, オブジェクト)返すようなイテレーターを返すクラスです.


``` Python
class MyEnumerate:
    def __init__(self, iterable, start=0):
        self.iterator = iter(iterable)  # イテラブルオブジェクトのイテレータを取得
        self.index = start

    def __iter__(self):
        return self

    def __next__(self):
        # イテラブルオブジェクトの次の要素を取得
        # StopIteration例外が発生した場合は、そのまま例外を呼び出し元に伝播させる
        element = next(self.iterator)
        result = (self.index, element)
        self.index += 1
        return result

st="apple"
for i,s in MyEnumerate(st) :
    print(str(i)+s)

# 0 a
# 1 p
# 2 p
# 3 l
# 4 e

```

> タプル`(a,b)`とは集合論的には順序対$(a,b)$です. 順序対とは
$(a,b)=(c,d)\Leftrightarrow a=b\mbox{かつ}c=d$
を満たすものです

 Pythonでは `a,b=c,d`や`a,b=(c,d)`とタプルを代入できる. for文の意味を考えると`MyEnumerate(st)`から受け取ったイテレーターの`next()`関数が呼び出されてそれが`i,s`に代入されている. 

##### `zip()`クラス

`zip()`はイテラブルなオブジェクトを複数受け取って,それぞれ受け取ったイテラブルオブジェクトの中身をペアにしたタプルを返すようなイテレーターを返すクラスだ. 

```Python
class MyZip:
    def __init__(self, *iterables):　# 可変のイテレーターを受け取れるようにする
        # 引数で受け取ったイテラブルオブジェクトのイテレータをリストに格納
        self.iterators = [iter(it) for it in iterables]

    def __iter__(self):
        return self

    def __next__(self):
        # 各イテレータから次の要素を取得してタプルにまとめる
        # いずれかのイテレータが要素を返さない場合（StopIteration例外を発生させる場合）、
        # MyZipのイテレーションも終了する
        zipped = tuple(next(it) for it in self.iterators)
        if not zipped:
            raise StopIteration
        return zipped

# 使用例
iterable1 = [1, 2, 3]
iterable2 = ['a', 'b', 'c']
iterable3 = [0.1, 0.2, 0.3]

for item in MyZip(iterable1, iterable2, iterable3):
    print(item)
```

### ジェネレーター

ジェネレーターはイテレーターを楽に生成するための仕組みです. 独自のイテレーターを作成する際に毎回, クラスを作っていては大変です.　ジェネレーターを使うと楽にイテレーターを非常に簡単にイテレーターをつくることができます.

- [x] `iter()`関数で作成　... イテラブルオブジェクトからイテレーターをつくる　　　
- [x]  クラスで直接的に定義    ...  特殊メソッドで`__iter__()`, `__next__(0`を定義する. 
- [ ] ジェネレーター関数で定義 ... `def`と`yield`文で定義
- [ ] ジェネレーター式で定義　 ... ジェネレーターの内包表記で定義

4つのうち2つは学びました. このセクションではジェネレーター関数とジェネレーター式を学びましょう.

### ジェネレーター関数

##### `yield`文を使ったジェネレーター関数

ジェネレータ関数は呼び出されても中身の関数のコードは呼び出された時点では実行されません. ジェネレーター関数が呼びだれたときに返すものはイテレーター（ジェネレータオブジェクト）です.  　ジェネレーター関数の中のコードが実行されるのは返された,イテレータオブジェクトについて`next()`関数を呼び出されたときで, ジェネレータ関数は次の`yield`まで実行されて,その値を返します.

この説明だとよくわからないとおもいますので,ジェネレーターによるフィボナッチイテレーターの実装をクラスによる実装と見比べてください.

先の例で定義したフィボナッチ数列のイテレーターのクラスとほぼ挙動が同じものがジェネレーターを使うと次のように簡単に定義できます.

```Python
def fibonacciIterator(first=1, second=1):
    a, b = first, second
    while True:
        yield a
        a, b = b, a + b

fib=fibonacciIterator(1,1)
next(fib)
# 1
next(fib)
# 1
        
```

ジェネレーター関数の中身の処理は`next()`関数が呼び出されると実行されて, `yield`で中断され, 再び`next()`関数が呼び出されると途中から実行されます. また, `Alphabet()`イテレーターのクラスと同等の機能をジェネレーターで実装できる. 

```Python
def alphabet(start, end):
    current = ord(start)  # 開始文字のUnicodeコードポイント
    end = ord(end)  # 終了文字のUnicodeコードポイント
    while current <= end:
        yield chr(current)  # 現在の文字を返す
        current += 1  # 次の文字へ

# 使用例
for char in alphabet('a','e'):
    print(char)
```

`Alphabet()`イテレーターのクラスとの重要な違いは`StopIteration`を明示的に書いていない点ですが, `next()`関数が呼び出されて処理が進んだ際にブロックから抜けるときがくると思います. その際に`StopIteration`が起こります. 

##### ジェネレーター関数内の`return`文

`return`文と`yield`文を混在させても問題ありません.`return`とはブロックから抜けることを意味します. ジェネレーター関数のブロックから抜けると`StopIteration`が起こるので, `return`文をかくことでただちに`StopIteration`を起こすことができます.

`return`に返す値は`StopIteration`という例外クラスの`value`属性に値が渡される. 

```Python
def gene():
    yield "Hello"
    return "World"

gen = gene()

try:
    next(gen)  # "Hello" を返す
    next(gen)  # ここで StopIteration が発生する
except StopIteration as e:
    print("Return value:", e.value)  # "World" を出力
```


##### ジェネレーターをくっつける`yield from`文

`yield from　[Iterable Object]`はイテラブルオブジェクトをジェネレーターの中に組み込むことができる機能です. 2つ以上のイテタブルオブジェクトをつなげてたり, 分岐させてりできる機能だと考えるとわかりやすいかもしれません.

第$n$項までフィボナッチ数列のイテレーターを返すジェネレーターを次のように再帰的な書き方ができます.
```Python
def fibonacci(n, first=1, second=1):
    if n == 0:
        return
    yield first
    yield from fibonacci(n-1, second, first+second)

# 使用例
N = 10  # 生成したいフィボナッチ数列の項数
for num in fibonacci(N):
    print(num)
```
### ジェネレーター式

内包表記でイテレーターを作成することもできます.最も簡易的なイテレーターの作成方法です.基本的にはイテラブルオブジェクトをいじって別のイテラブルオブジェクトをつくります.. ジェネレーター関数よりさらに簡単に定義できます.

```Python
# n以上の自然数を返すジェネレーター
def natural(n) :
    while True :
        yield n
        n+=1
          
sq=(n**2 for n in natural(0))
# 0 1 4 9 16 25 ...

li=(n*3+1 for n in natural(0))
li=(n for n in natural(0) if x%3==1)
# 1 4 7 10 13 ...

lo=(n if x%3==1 else 0 for n in natural(0))
# 0 1 0 0 4 0 0 7 0 0 10 0 0 13 ...

n=10
combinations=((x,y,n-x-y) for x in range(n+1) for y in range(n-x+1))
# (0,0,10),(0,1,9),(0,2,8)...,(0,10,0),(1,0,9),(1,1,8),(1,2,7),...,(10,0,0)
```
> 内包表記は数学の集合の内包表記に近い.  
平方数の集合$S=\lbrace n^2 |n\in \mathbb N \rbrace$
$L=\lbrace n |n\in \mathbb N, n≡1({\rm mod \ 3}) \rbrace=\lbrace 3n+1 |n\in \mathbb N \rbrace$


### 遅延評価

最後に遅延評価の観点から, リストとイテレーターの違いを説明します. 遅延評価は,値が必要になるまでその計算を遅らせる戦略です.

$10000$円札, $5000$円札,$1000$円札が合わせて$N$枚あるとき, 金額が$Y$円となる組み合わせを1つ見つけて, 存在しない場合はそれを判定するプログラム[問題出典](https://atcoder.jp/contests/abc085/tasks/abc085_c)を作成します.それを,リストとジェネレーター式を使った実装を見比べてみましょう.

```Python
# リストを使った実装
N,Y=2000,20000000

combinations = [(i,j-i-1,n+1-j) for j in range(n+2) for i in range(j)]
condition = lambda tup: 10000 * tup[0] + 5000 * tup[1] + 1000 * tup[2] == y #yは定数
solutions = list(filter(condition, combibations))

print(solutions[0] if solutions else (-1, -1, -1))

# 実行時間: 420 ms
# メモリ	297 MB
```


```Python
# ジェネレーター式を使った実装
N,Y=2000,20000000

combinations = ((i,j-i-1,n+1-j) for j in range(n+2) for i in range(j))
condition = lambda tup: 10000 * tup[0] + 5000 * tup[1] + 1000 * tup[2] == y #yは定数
solutions =filter(condition, combibations)

print(next(solutions,(-1,-1,-1)))

# 実行時間: 367 ms
# メモリ	12 MB
```
リストの内包表記を使った実装では

   - `combinations` リスト内包表記：全ての可能な組み合わせを一度に生成し, メモリに保持しています. 
   - `list(filter(...))`: 全ての要素に対して条件をチェックし,条件を満たす全ての要素を新しいリストに格納します.

ジェネレーター式を使った実装では

   - `combinations` ジェネレータ式：全ての可能な組み合わせを一度に生成するのではなく、必要に応じて1つずつ生成します.
   - `filter()` 関数：ジェネレータに対して適用されるため、全ての要素を処理する前に条件を満たす要素が見つかれば処理を停止します.
   - `next()` 関数：最初に条件を満たす要素のみを取得し,それ以上の処理は行いません.

このような「式の評価を値が必要になるまで遅らせる戦略」, 遅延評価を使うと,不要な計算を回避し, メモリー使用効率を改善できる可能性があります. 今回の例だとメモリー使用量が25倍程度差が出ました.