dict遊び -- 絵を描く人の余暇のらくがきとコードを書く人の余暇の何か
[poem][python] dict遊び
ポエムです。長いです。
はじめに
絵を描くことが好きだった人が絵を描く仕事につく。絵を描くことを仕事にしている人がたまたま余暇にらくがきの絵を描く。仕事でも絵を描いているのだからもう描かなくても良いじゃないかという声もかけられるが、余暇の落書きは仕事としての絵とは何だか違うような気がして、やっぱり余暇にらくがきをする。
みたいなことがプログラミングにもあるのではないかということを最近良く思う。これは個人的な話でありすごく主観的な捉え方によるものだけれど。絵を描くという領域における余暇の落書きに類するような行為をコードを書くという領域上で行っているような気がした。いろいろ思い返してみると息抜きとしてのプログラミングというものが自分自身の中には存在している気がする。それは面白そうなアプリケーションやライブラリを探すなどのいわゆる情報収集とも違うものではあるし、何か作りたいアプリケーションが存在していてそのアプリケーションを開発するというのとも違う気がする。
コードを書くことで自分の中にあるストレスが消えていくような、いわゆる息抜きとしての行為のプログラミングがどういうものかということを、とりとめもなく書いてみることにした。もちろんすべての人がやっているわけではないし。万人に当てはまるようなものではないけれど。
コードを書くときの楽しさ
コードを書くいった時に思いつくものは以下の様なものだった。
何らかの領域上に何らかの日常的な動作・処理が存在していて、それを機械に実行可能な形に翻訳すること
何らかの動作が存在していてそれをなぞるような形で振る舞いを記述するということがある種のデッサンに似たような感じを受ける。そのような何らかの振る舞いの記述をコーディングと呼んでいるような気がする。そして大抵の場合、コーディングと言った場合にスキルという言葉もセットになってついてくる事が多いが、今回はそのスキルに関しては全く触れるつもりはないし。スキルを向上するためにどうすれば良いかみたいな話はしない。ただただ趣味という意味でコードを書くということをしている事があるようなきがする。
そのコードを書く楽しさとはなんだろうかみたいなことを例をあげてどうにか文章という形で表現してみたい。
dict遊び
pythonのdict
pythonにはdictという組み込みの型が存在する。このdictは他の言語では連想配列と呼ばれたりマップと呼ばれたりすることもあるかもしれない。例えばweb apiのレスポンスがJSONの形式で返されるような時に、そのレスポンスをpython上に持ってきたときにはdictの型の値にデコードされてきたりする。
d = {"x": "a", "y": "b", "z": "c"}
d["y"] # => "b"
基本的にはkeyとvalueのpairになっていて、渡したkeyに対応するvalueが存在する場合にそれが結果として返ってくる。上の例ではdictのkeyのvalueも文字列だけれどもちろんvalueをdictにしたdictを作ることもできる。そしてそのdictのvalueもまたdictになって...というように再帰的にdictを持ったdictはツリー状の構造になる。実際web apiのレスポンスもそのようなツリー構造のデータが返ってくる事が多い。
d = {
"x": {
"a": {
"i": 10,
},
},
"y": {
"a": {
"j": 20,
},
},
"z": {
"a": {
"k": 30,
},
},
}
d["y"]["a"]["j"] # => 20
dictへのアクセス
任意の深さへのアクセス
どこに何が入っているか完全にわかっている場合にはただただkeyとして渡していけば良い。とは言え深さが異なる位置にアクセスしたくなる事があるかもしれない。ある値は d["a"]["b"] で済むかもしれないし d["x"]["y"]["z"] と3回のアクセスが必要かもしれない。この特定の値を取得するために必要なkeyの列をpathと呼ぶことにする。pathの長さは不定で、あるものは2かもしれないし。またあるものは5などかもしれない。
そのようなパスを受け取って望みの値を取るような処理は書けるかというとたぶん以下の様になる。
def access(d, path): for k in path: d = d[k] return d access(d, ["x", "y", "z"]) # == d["x"]["y"]["z"] access(d, ["a", "b"]) # == d["a"]["b"]
任意回のアクセス
このような関数が書けると何が嬉しいかというと、値の位置さえわかっていれば、値の深さによらず望みの値を一気に取得する処理を書くことができるようになる。例えばコストの様な数を取り出してその合計を計算してみる。
def sum_cost(tree, path_list): total = 0 for path in path_list: total += access(tree, path) return total
今度は、深さが不定なツリーから値を1つ取れるだけでなく、ツリー状のdictから好きな個数の値(上の例ではコスト)を一気に取得する事ができた。あるいはここでちょっと考えてsumという関数があるから使えば短くなると考えて以下のように書くかもしれない。
def sum_cost(tree, path_list): return sum(access(tree, path) for path in path_list)
こういう風に同じ処理を短くあるいはより手軽に書けないかと考えるが楽しいというときもあるかもしれない。上手く短く書けたときには頭の中が整理されたような気がする。
あやふやな存在への対応
誤ったpathを含んだリスト
先程の例では全ての欲しい値の位置が分かっている状態について考えていた。実際には値の位置が分かっていない事が多いかもしれない。
例えば、[["a","b","c","cost"],["x","y","cost"], ["i","cost"]] などというpathのリストが渡されたとして ["x","y","cost"] というpathには値が存在していないかもしれない。そういう場合にも適切に合計を計算したい。
とは言え存在しないpathを指定してしまった場合の対応をすることはそんなに難しくない。accessの部分を存在しなかった場合には何にも影響を与えない値を返すようにして使える特別版に置き換えれば良い。例えば以下の様な関数を作る。
def maybe_access(d, path, default=None): for k in d: if k not in d: return default d = d[k] return d
この関数をaccessの代わりに使えば誤ったpathを含んだリストを受け取ったとしても正しい合計値を返す事ができる。
def sum_cost(tree, path_list): return sum(maybe_access(tree, path, default=0) for path in path_list)
不完全なpathでのアクセス
誤ったpathを含んだリストだけではなく、そのpathが不完全であるかもしれない。例えば、正確には d["x"]["y"]["z"]["cost"] であるかもしれない。ところが分かっているのは必ず "y" が途中にある "cost" で終わる値を取りたいということかもしれない。これはちょっと頭を捻る必要がある。つまり something(d, ["y", "cost"]) で先程の d["x"]["y"]["z"]["cost"] の値を取ってきたい。また別のところでの位置は d["x"]["y"]["z"]["x"]["y"]["z"]["cost"] というような形かもしれない。このような末尾と途中の一部だけが分かるpathから値を取得する関数を考えてみる。
from collections import deque def gentle_access(d, path): r = [] _gentle_access(d, deque(path), r) return r def _gentle_access(d, path, r): if len(path) == 0: r.append(d) if not hasattr(d, "keys"): return for k in d.keys(): if k == path[0]: q = path.popleft() _gentle_access(d[k], path, r) path.appendleft(q) else: _gentle_access(d[k], path, r) d = { "x": {"y": {"z": {"i": {"cost": 10}}}}, "i": {"cost": 20}, "z": {"y": {"z": {"i": {"x": {"y": {"z": {"i": {"cost": 30}}}}}}}}, } gentle_access(d, ["y", "cost"]) # => [10, 30]
再帰がでてきたが全部取得する事ができた。もちろん頑張りすぎないように探索する深さを制限しても良いし。条件に合致したらすぐに1つだけ返すように変えてみても良い。
値を取得したいのではなくツリーを変更したい場合
毎回探索するのも馬鹿馬鹿しいのでたどり着いた値を浅い場所に保持するようにしてみよう。例えば上の例のdictを渡すと以下のようになる操作を考えてみる。
d = {
"x": {"y": {"z": {"i": {"cost": 10}}}},
"i": {"cost": 20},
"z": {"y": {"z": {"i": {"x": {"y": {"z": {"i": {"cost": 30}}}}}}}},
}
simplify(d, ["y", "cost"])
d2 = {
"x": {"y": {"z": {"i": {"cost": "$cost/x"}}}},
"i": {"cost": 20},
"z": {"y": {"z": {"i": {"x": {"y": {"z": {"i": {"cost": "$cost/z"}}}}}}}},
"$cost": {
"x": 10,
"z": 30,
},
}
今度のd2の方のtreeの方ではコストが欲しい場合には $cost の中だけ観れば良いようになった。同じkeyのものがあったら衝突してしまうから実はリストにしたほうが良いなどもあるかもしれない。この変更の操作を記述するにはどうしたら良いんだろう。
条件に合致した時に変更を加える関数を渡す場合
関数の引数に関数を渡すこともできる。以前に定義した不完全なpathでのアクセスを行う関数に関数を渡せるように改造することを考えてみる。以下の様になる。
def walk(d, path, fn): _walk(d, deque(path), fn) def _walk(d, path, fn): if len(path) == 0: return if not hasattr(d, "keys"): return for k in d.keys(): if k == path[0]: q = path.popleft() if len(path) == 0: fn(d, k) else: _walk(d[k], path) path.appendleft(q) else: _walk(d[k], path) def simplify(data, path): for top_key in data.keys(): def modify(d, k): data["$cost"][top_key] = d[k] d[k] = "$cost/{}".format(top_key) walk(data[top_key], path, modify)
上手くいっていそう。
d = {
"x": {"y": {"z": {"i": {"cost": 10}}}},
"i": {"cost": 20},
"z": {"y": {"z": {"i": {"x": {"y": {"z": {"i": {"cost": 30}}}}}}}},
}
simplify(d, ["y", "cost"])
# {
# 'x': {'y': {'z': {'i': {'cost': '$cost/x'}}}},
# 'z': {'y': {'z': {'i': {'x': {'y': {'z': {'i': {'cost': '$cost/z'}}}}}}}},
# 'i': {'cost': 20},
# '$cost': {'x': 10, 'z': 30}
# }
実行した結果x,zの値が$costに移動している。そして元々値があった場所には$costから辿るための道筋が記されている(e.g. "$cost/z"のことなどを指している)。上手くいっていそう。本当に？すこしだけ考えてみると途中の意味を良く決めていない状態のままコードを書いていた。例えば、"y" から始まるdict。こういう値はどうなるべきだろう？
d3 = {"y": {"x": {"cost": 100}}}
途中の意味に開始地点も入るのならこれも $cost にまとめられる対象に含まれて欲しいかもしれない。以下のように。
d3 = {
"y": {"x": {"cost": 100}},
"$cost": {"y": 100},
}
少しコードを変えてみる。
def simplify2(data, path): path = deque(path) data.setdefault("$cost", {}) for top_key in data.keys(): def modify(d, k): data["$cost"][top_key] = d[k] d[k] = "$cost/{}".format(top_key) if path[0] == top_key: q = path.popleft() walk(data[top_key], path, modify) path.appendleft(q) else: walk(data[top_key], path, modify) d3 = {"y": {"x": {"cost": 100}}} simplify(d3, ["y", "cost"]) # {'$cost': {'y': 100}, 'y': {'x': {'cost': '$cost/y'}}}
dequeの利用が二重になっている部分が気に入らないところではあるけれど。一応作りたかった答えを作る事はできている。
条件に合致した時、その位置の物を直接返すようにする場合
もしかしたらの話、たとえば先程の処理を以下のような形で書けるとしたらどうだろう。
for top_key, iterator in simplify3(d, ["y", "cost"]): for k, sd in iterator: if "$cost" not in d: d["$cost"] = {} d["$cost"][top_key] = sd[k] sd[k] = "$cost/{}".format(top_key)
今度は欲しい値がこちらに直接やってくるので関数を受け渡す必要がない。このように書ければもう少し先程の処理なども気軽に掛けたのかもしれない。
最後の値だけではなく途中の値も全て欲しい場合
あるいは最後の値だけではなく途中の値も全て欲しい場合もあるかもしれない。例えば今までpathとして渡していた値は ["y", "cost"] だったが、この "y" の階層でも何か副次的な処理が行いたい場合もあるかもしれない。この場合はどうにかすることができるだろうか？ 例えば以下の様になってほしい。
modify(d, ["y", "cost"]) { 'z': {'y': {'z': {'i': {'x': {'y': {'z': {'i': {'cost': '$cost/z'}}}}}}}}, 'x': {'y': {'z': {'i': {'cost': '$cost/x'}}}}, 'i': {'cost': 20}, '$cost': {'x': 10, 'z': 30}, '$ys': [ {'z': {'i': {'x': {'y': {'z': {'i': {'cost': '$cost/z'}}}}}}}, {'z': {'i': {'cost': '$cost/x'}}}, ], }
今度は$costの他に$ysも現れてそのyの階層以下の値を別途$ysに持ちたい。もちろん先程のwalkを何度も使えばできるが酷い形になる。
for top_key in list(d.keys()): def on_y(d1, k1): def on_cost(d2, k2): if "$cost" not in d: d["$cost"] = {} if "$ys" not in d: d["$ys"] = [] d["$cost"][top_key] = d2[k2] d2[k2] = "$cost/{}".format(top_key) d["$ys"].append(d1[k1]) walk(d1, ["cost"], on_cost) walk(d[top_key], ["y"], on_y)
同じ名前の位置に対して同じ処理を行いたい
さらに酷い形を進めてみよう。たとえば、a,b,a,b,a,b,a,b,a,bと続いていく木に対してaのときにだけ何らかの処理を付け加えたい場合にはどうすれば良いだろう？これももちろんアクセス用の関数を何度も書けばこなすことができる。
def on_a0(d0, k0): something(d0[k0]) def on_a1(d1, k1): something(d1[k1]) def on_a2(d2, k2): something(d2[k2]) def on_a3(d3, k3): something(d3[k3]) def on_a4(d4, k4): something(d4[k4]) def on_a5(d5, k5): something(d5[k5]) walk(d4, path, on_a5) walk(d3, path, on_a4) walk(d2, path, on_a3) walk(d1, path, on_a2) walk(d0, path, on_a1) walk(d, path, on_a0)
しかしこれは馬鹿馬鹿しい。ところで自分自身を返す事はできないのだろうか？例えば操作関数がもう１つ引数を取り、引数自体が自分自身を返すみたいな構造。もしそれができるなら以下の様に書けるはず。
def on_a0(walker, d0, k0): something(d0[k0]) walker(d0[k0]) walk(d, path, on_a0)
あるいはpathの探索をその階層のkeyの一致のみで調べていたが。幾つかのkeyの内のどれか１つと当てはまるのような一致条件の変更などはできるだろうか？もっというと一番最後の再帰の例のように繰り返しの構造を引数として取得して使うことはできないだろうか？あれこれコードをイジった結果自分自身を使う処理をこういう形で書ける様になったりする
import unittest class WalkerTests(unittest.TestCase): def _getTargetClass(self): from my import LooseDictWalker return LooseDictWalker def _makeOne(self, *args, **kwargs): return self._getTargetClass()(*args, **kwargs) def test_chains2(self): from my.walkers import SimpleContext from my.operators import ANY class RecContext(SimpleContext): def __init__(self, qs): self.qs = qs[:] def __call__(self, walker, fn, value): return fn(walker, self, value) s = [] def matched(walker, ctx, value): s.append(value) walker.walk(ctx.qs[:], value, ctx=ctx) d = {"a": {"b": {"a": {"b": {"a": {"b": 10}}}}}} qs = [ANY, "b"] self._makeOne(on_container=matched).walk(qs, d, ctx=RecContext(qs)) expected = [ {'b': {'a': {'b': {'a': {'b': 10}}}}}, {'b': {'a': {'b': 10}}}, {'b': 10} ] self.assertEqual(s, expected)
加えてある程度、変更用の関数の引数の形式も自由にできる。例えば以下のようなPathContextを定義すると、その時点まで辿った状態を(パンくずリストの様な履歴)を受け取る事ができるようになる。
class PathContext(object): def __init__(self): self.path = [] def push(self, v): self.path.append(v) def pop(self): self.path.pop() def __call__(self, walker, fn, value): return fn(self.path, value)
というようなことをしていた。こういうちょっとしたコンパクトな処理に対する何らかのアイデアから端を発して不満を解決しつつ、より広い領域に対しても、意図していた通りの振る舞いさせる記述ができないか考えながら変更を加えるみたいな作業が気晴らしになっているらしい。
おまけ
ちなみに最後の例ででてきたwalkerは現時点ではこういう実装
class SimpleContext(object): def push(self, ctx): pass def pop(self): pass def __call__(self, fn, walker, value): return fn(value) def apply(q, v): if callable(q): return q(v) else: return q == v class Any(object): __repr__ = repr def __call__(self, v): return True ANY = Any() class LooseDictWalker(object): context_factory = PathContext def __init__(self, on_container=None, on_data=None): self.on_container = on_container self.on_data = on_data def on_found(self, ctx, d, k): if self.on_container is not None: ctx(self, self.on_container, d) if self.on_data is not None: ctx(self, self.on_data, d[k]) def walk(self, qs, d, depth=-1, ctx=None): ctx = ctx or self.context_factory() return self._walk(ctx, deque(qs), d, depth=depth) def _walk(self, ctx, qs, d, depth): if depth == 0: return if not qs: return if hasattr(d, "keys"): for k in list(d.keys()): ctx.push(k) if apply(qs[0], k): q = qs.popleft() self._walk(ctx, qs, d[k], depth - 1) if len(qs) == 0: self.on_found(ctx, d, k) qs.appendleft(q) else: self._walk(ctx, qs, d[k], depth) ctx.pop() return d elif isinstance(d, (list, tuple)): ctx.push("[]") for e in d: self._walk(ctx, qs, e, depth) ctx.pop() return d else: return d
invalid recursive type XXX
zero valueを設定する際に循環してしまうと無限に再帰してしまい終わらないという話。
例えば以下のような定義はダメ。
自分自身で再帰
type Tree struct { Value int Left Tree Right Tree }
もちろん、ポインターにしてあげれば、nilがzero valueになるので無限に再帰はしなくなる。
type Tree struct { Value int Left *Tree Right *Tree }
相互再帰(N=2)
自分自身の型で再帰的に定義してはダメというルールではない。初期化時のiterationで循環参照が起きれば無限再帰が起きる。こういうのもダメ。
type L struct { R R } type R struct { L L }
どれか１つでもnilになればそこが終端になるので以下はOK。
type L struct { R R } type R struct { L *L }
N=3
もちろん3つ組の循環でもダメ。
type A struct { B B } type B struct { C C } type C struct { A A }
循環しなければただの木なのでいつかは終端に辿り着く。
type T0 struct { T1 T1 } type T1 struct { T2 T2 } type T2 struct{}
