探検３兄弟、イテレタ、インタプリタ、ビジター
このワークシートはMath by Codeの一部です。
１．探索は日常茶飯事
探検というコトバからどんなようすをイメージしますか？
幅広く舗装されたまっすぐの太い通りをひたすら直進する。
これを探検といいませんよね。
探検という感じがするのは、道が曲がりくねっていて、
先が見えない、樹木やぬかるみが邪魔をする。
行き止まりがあるかもしれない。
まさに迷路の探索だ。
でも、探索というのは冒険家の専売特許でないです。
みなさんがふだん使っているPCやスマホでも探索はある。
そう、データ探索だね。
今回は身近なデータ探索につながる３つのパタン、
イテレタ、インタプリタ、ビジター
題して、探索３兄弟をやろう。
１．イテレタは順次検索共通仕様だ。
＜イテレタ＞
イテレタiteratorは反復iterするもの反復子のことです。
GOF本では、
イテレタ：
集約オブジェクトの内部が公開されてなくても、その要素に順にアクセスすることを助ける。
たとえば、本棚の並ぶ本の値段はカバーの後ろにかいてありますが、
自分の持ってる本で、一番定価が高い本を探したいとしよう。
本棚に本が何冊あるかは別として、
一番上の段からみる、１つの段は左から順にみる。
一番下の段の一番右の本が最後の本になる。
本棚の本たちをbooksとしよう。
そこで、
python なら、
for book in books:
print(book.price)
この順番に見る働きをクラスに格上げしたものがイテレタモジュールです。
イテレタを使うには、反復できるオブジェクトを用意します。
イテラブル（順に進める）なアグリゲート（集約オブジェクト）です。
順不同でよい集まり例えば、マップ、辞書、セット（集合）はイテラブルではありません。
イテラブルはnext（次）をつかって、順番に調べるのですね。
つまり、最初から最後まで順番がつく集まりを順に調べるクラスがイテラブルです。
なんて、地味なんでしょうね。
なんで、こんな単純なパタンに名前をつけたのでしょうか。
それは、順番をつけて全件調べるという地味な調査が一番確実でよく使われるからです。
さらに大切なのは、インターフェース、共通キーワードを決めておくと、
調べる対象が変化しても、調べる対象の実装が混ざっていても平気になるからです。
イテラブルな調査対象は、リストと配列とタプルくらいですが、
それが変更になっても、まざっていも大丈夫。
ユーザーは同じキーワードで調査をイテラブルさんに対してお願いできちゃうのですから。
それでは、実装してみよう。
昔、「世界のナベアツ」というのがはやりました。
３の倍数か３のつく数のときに変顔をするという芸人です。
ふつうに考えると、１から順に整数Nを表示していくのですが、
整数Nが「３の倍数」（A条件）か「３のつく整数」（B条件）のときに、「変顔」を表示するので、
NがAまたはBであることをif文で作り込むのが普通のプログラミングでしょうね。
あえてこれを、イテレタパタン、順次検索共通仕様でやってみましょう。
ナベアツイテレタというインターフェースを作ります。
調査の最大数100のコンストラクターを持ちます。
nabe(x)というメソッドを持ちます。
この子クラスが３の倍数リストイテレタmulti3と３のつく整数リストイテレタhasDidit3です。
ともにnabe(x)というメソッドをもち、リストに属するときはtrueを返します。
だから、
M= multi3()
D=hasdDigit3()
でインスタンスを作れば、
ユーザーは
for i in range(1,100+1):
if M.nabe(i) or D.nabe(i):
print("変顔”)
else:
print(i)
とするだけです。
multi3とhasDigit3の中身を知らなくてもよいのです。
たとえば、multi3は0,1,2,3,4,5,.....のインデックス順に{true, false, false, true, false,false,....}というリストを
作っているかもしれません。それとも単純に３の倍数のリストにしているかもしれません。
一方のhasDigit3は
A={ 30+x for x in range(10)} , B={ 3+ 10 x for x in range(10)},C={33}
D=list(（A｜B） - C)のように、集合演算で作っているかもしれません。
このようにリストの作り方は違いますが、
nabe(n)の実装をしておけば、ユーザーは同じ命令が使えます。
さあ、実装してみよう。
＜順次検索共通仕様＞
#nabeatsu.py
# ==========================================
# 【インターフェース】ナベアツイテレータの共通契約
# ==========================================
class NabeatsuIterator:
"""内部のリスト構造がどうであれ、共通のキーワード『nabe(x)』を保証する"""
def __init__(self, max_num=100):
self.max_num = max_num
self.target_list = self._create_list() # 子クラスごとに異なるリストが作られる
def _create_list(self):
"""【型枠】リストの具体的な作り方は子クラスに委ねる"""
raise NotImplementedError()
def nabe(self, x):
"""ユーザーが使う共通キーワード。リストに属していればTrueを返す"""
return x in self.target_list
# ==========================================
# 【子クラス1】3の倍数リストイテレータ（数理的なアプローチ）
# ==========================================
class Multi3Iterator(NabeatsuIterator):
def _create_list(self):
# 1からmax_numまでの間で、3の倍数だけを格納したリストを作る
return [i for i in range(1, self.max_num + 1) if i % 3 == 0]
# ==========================================
# 【子クラス2】3のつく整数リストイテレータ（集合を駆使したアプローチ）
# ==========================================
class HasDigit3Iterator(NabeatsuIterator):
def _create_list(self):
# 10の位が3の集合
A = {30 + x for x in range(10)}
# 1の位が3の集合
B = {3 + 10 * x for x in range(10)}
# 重複する33の集合
C = {33}
# 集合の和（OR）から重複を引き、1からmax_numに収まるものだけをリスト化
union_set = (A | B) - C
return [i for i in range(1, self.max_num + 1) if i in union_set]
# ==========================================
# 【実行・ユーザー側のコード】中身を知らなくても、同じ命令で全件調査！
# ==========================================
# 1. 異なる内部実装を持つ、2つのイテレータインスタンスを生成
M = Multi3Iterator(100)
D = HasDigit3Iterator(100)
print("ナベアツさん登場！ \n")
# 2. ユーザーは共通の「nabe(i)」だけで、1から100まで確実に走査する
for i in range(1, 100 + 1):
# Mの中身が倍数リストか、Dの中身が集合演算か、ユーザーは一切知らなくてよい
if M.nabe(i) or D.nabe(i):
print("（変顔）", end=" ")
else:
print(f"{i}", end=" ")
# 10個ごとに改行して見やすく整える
if i % 10 == 0:
print()
[OUT]
1 2 （変顔） 4 5 （変顔） 7 8 （変顔） 10
11 （変顔） （変顔） 14 （変顔） 16 17 （変顔） 19 20
（変顔） 22 （変顔） （変顔） 25 26 （変顔） 28 29 （変顔）
（変顔） （変顔） （変顔） （変顔） （変顔） （変顔） （変顔） （変顔） （変顔） 40
41 （変顔） （変顔） 44 （変顔） 46 47 （変顔） 49 50
（変顔） 52 （変顔） （変顔） 55 56 （変顔） 58 59 （変顔）
61 62 （変顔） 64 65 （変顔） 67 68 （変顔） 70
71 （変顔） （変顔） 74 （変顔） 76 77 （変顔） 79 80
（変顔） 82 （変顔） （変顔） 85 86 （変顔） 88 89 （変顔）
91 92 （変顔） 94 95 （変顔） 97 98 （変顔） 100
２．インタプリタは通訳一式
＜インタプリタは通訳一式＞
インタプリタというのは、その名の通り通訳ですね。
通訳するのは今はAIもやりますが、人間のイメージが強いですね。
同時通訳は聞いてるだけで大変そう。忙しそうだし。
でも、インタプリタは楽ですよ。
なにしろ、文法から何からはっきりしているからです。
たとえば、RPNという計算記法があります。
逆ポーランド記法の略で、
中身は演算を真ん中にかくふつうの記法（中置）A＋Bを「AB+の順にかく（後置）記法」のことです。
後置記法RPNの何がよいかというと、
中置だと、かっこのある式 (1 + 2) × 3
これを後置にすると、 1 2 + 3 ×
で、いいのです。
前とか中というコトバは数式ができあがってから人間が名付けた言い方です。
これをPCがわかるように伝えないと、プログラミングには使えません。
それがインタプリタです。
そう、PCにわかるように文法と単語まで教えます。それが、BNF情報です。
１けたの計算をするRPNをBNF（バッカス・ナウア式）で表します。
BNFの基本記号は３つです。
A::= B: 「AはBで定義される」
A|B : 「AまたはB」
＜A＞：Aは構成要素
RPNのルールは３つです。
＜digit＞ ::= 0 | 1 | 2 | ... | 9
＜operator＞ ::= + | - | * | /
＜expression＞ ::= ＜digit＞ | ＜expression＞ ＜expression＞ ＜operator＞
数式の定義が自己参照しているからこそ再帰的に読み取ることができるのですね。
さて、データ構造といえばスタックかキューかハッシュの出番かな？
左から順に、つまり入れた順に使うわけではないから、スタックでしょうか。
stackにSさんと名前をつけよう。
RPN＝「4 3 2＋ 1 ー ＊」を空白区切りでSさんにわたそう。
Sさんは数値ならどんどん上に積んでいく。
Sに左から4、3、2の順を渡すと、上か順にｘ、ｙ、残りをysと名付けるなら、x=２, y=３, ys=４となる。
もとの式の左右の順番とｘ，ｙの順番が逆になってしまうので計算順に注意しよう。
次は（＋）が出たから、上からx=２,y=３を取り出して、y+x=３+２=５をSさんに戻す。
残った４の上に５が積まれるので、上から順にx=5,y=4となる。
次の1はSさんに渡す。Sさんは上から順にx=1,y=5,ys=4となる。
次は（ー）が出たから、上からx=1,y=5を取り出して、y-x=5-1=4を戻す。
Sさんは上から順にx=4,y=4となる。
次も（＊）が出たから、上からx=4, y=4を取り出し、y*x=4*4=16を戻す。
x=16が入っている。
RPNが空になったとき、Sさんのスタックが１つの数値だけになりそれが答えになるね。
＜RPNインタプリタをHaskellで作ってみよう。＞
RPN=文字列を受取り、和を返す関数calcDiff( RPN)を作ってみよう。
文字列RPNをリストLに分解するwords関数を作っておき、使おう。
Lを左から順に読み取って処理は、左畳み込みfoldl関数にfoldStack関数にLと空のリストを渡す。
最後に畳み込んだあとのリストの先頭をhead関数で読み込む。
この３つの関数をパイプラインでつないだ、合成関数がcalcDiffです。
ただし、foldStack関数だけは未定義なので、where句で末尾にケース分けして反応を定義します。
foldStack関数が使うスタック（だたのリストです）Sは最初は空です。S＝[ ]
Lからの読み取りが数値numなら, Sの中身xsの先頭にnumを追加する。Sの先頭から順にx,y,ysとなる。
Lからの読み取りが”-”なら,Sの先頭からx,yなので、y-xを計算してSの先頭に追加する。
最後にSの先頭(head)を読み取る。
これをHaskellでかくとこうなります。
calcDiff = head . foldl foldStack [] . words
where
foldStack (x:y:ys) "-" =(y-x):ys
foldStack xs num = read num :xs
ghci>calcDiff " 10 - 2 "
8
ghci>calcDiff " 2 - 10 "
-8
Haskellなら、読み取った演算記号が-以外の場合の式をwhere句に、好きなだけ追加するだけで
四則計算ができるように改造できます。
たとえば、sum や ln など、haskellが読める関数がそのままかけます。
calcRPN = head . foldl foldStack [] . words
where
foldStack (x:y:ys) "+" =(y+x):ys
foldStack (x:y:ys) "-" =(y-x):ys
foldStack (x:y:ys) "*" =(y*x):ys
foldStack (x:y:ys) "/" =(y/x):ys
foldStack (x:y:ys) "^" =(y**x):ys
foldStack (x:xs) "ln" = log x:xs
foldStack xs "sum" =[sum xs]
foldStack xs num = read num :xs
課題：juliaでRPNインタプリタをつくろう。
juliaにもfoldl,foldr関数があるのですが、簡単な演算のくり返しでは作動しますが、
一般の関数は難しいようです。仕方ないのでwhileで代用してます。
words関数とfoldStack関数を作っておき、単体で作動テストをしてから、
それらを組み込んだcalcRPN関数を動かしてます。
function words(x) # 1スペースで区切る
return split(x," ")
end
function foldStack(lst)
ope = ["*","+","-","/"]
opeS = Set(ope)
Stack =[]
item = popfirst!(lst)
# y x ope を抜き出して Stack の上からx ,y の順につまれた数で
# z= y ope x を計算します。
while item ∉ opeS
pushfirst!(Stack,item)
item = popfirst!(lst)
end
if item in ope
x = parse.(Int,popfirst!(Stack))
y = parse.(Int,popfirst!(Stack))
z = 0
if item == ope[1]
z = y * x
elseif item == ope[2]
z = y + x
elseif item == ope[3]
z = y - x
elseif item == ope[4]
z = y / x
end
end
#取り出した３要素y,x,opeを１要素zにしてリストlstに戻し、
#計算しなかったStackの残りも、リストlstにもどします。
pushfirst!(Stack,z)
while length(Stack)>0
p = string(popfirst!(Stack))
pushfirst!(lst,p)
end
return lst
end
function calcRPN(RPN)
res = RPN |> words
while length(res)>2
res = foldStack(res)
end
return parse.(Int,res)
end
"4 3 2 + 1 - *" |> calcRPN
#==========================
[OUT]
1-element Vector{Int64}:
16
課題：これを「Python」で実装してみよう。
from functools import reduce
def calcDiff(RPN: str) -> int:
"""【Interpreter】
逆ポーランド記法（RPN）の文字列を通訳し、数式の意味を解釈して計算結果を返す。
words ➔ foldl(foldStack) ➔ head のパイプライン合成。
"""
# 1. 【words関数】文字列をスペースで区切ってリスト（トークン列）に分解する
def words(text: str) -> list:
return text.split()
# 2. 【foldStack関数】左畳み込み(foldl)の各ステップで、スタックに値を積む、または計算する
# Pythonの reduce(foldl) に合わせて、第1引数をスタック(S)、第2引数を読み取った文字(item)とする
def foldStack(S: list, item: str) -> list:
operators = ["+", "-", "*", "/"]
if item in operators:
# 演算子を読み込んだ場合：スタックの先頭からx, yを取り出す（Sの先頭から順にx, yになる）
x = S.pop(0)
y = S.pop(0)
# 演算子に応じた計算を行い、結果zをスタックの先頭(xs)に戻す
if item == "+": z = y + x
elif item == "-": z = y - x
elif item == "*": z = y * x
elif item == "/": z = int(y / x) # 割り算は整数丸め
S.insert(0, z)
else:
# 数値を読み込んだ場合：整数に変換してスタックの先頭(xs)に追加する
S.insert(0, int(item))
return S
# 3. 【head関数】畳み込んだあとのスタックの先頭要素を読み込む
def head(S: list) -> int:
return S[0]
# ========================================================
# 【パイプライン合成の実行】
# 提示された数式「 1 2 + 3 * 」の文脈を、左から右へと畳み込んで解釈していく
# ========================================================
tokens = words(RPN) # ① words: 文字列をリストLに分解
final_stack = reduce(foldStack, tokens, []) # ② foldl: 空リスト[]からスタートしてトークンを畳み込む
return head(final_stack) # ③ head: 先頭の計算結果を回収
# ==========================================
# 【作動テスト】Juliaのサンプルと同じ数式で検証
# ==========================================
print("インタプリタ\n")
rpn_expr1 = "4 3 2 + 1 - *"
result1 = calcDiff(rpn_expr1)
print(f"RPN表記: {rpn_expr1}")
print(f"[OUT] ➔ {result1}")
RPNインタプリタ
３．振り返り
＜振り返り＞
ビジターを3番目に扱う予定だったけれど、
イテレタ、インタプリタにかなりの行数をとってしまた。
発想は単純だけれども、
実装するとなると場所をとってしまう。
やはり、
地味に確実に動くものを作るということは、
いざやってみると細かな設定とぬけのない記述が必要になり、
順次的な処理では、クラス数は少ないのに
１つ１つのクラスの処理が複雑に流れがちだからか。
ということで、ビジターを使った探検は次回のお楽しみにしよう。
上にあげた、geogebraで作ったRPNインタプリタの作り方は
calcRPN関数で電卓を作ろうのページの後半を参照してください。