ランレングス符号化をpythonで
タイトルに反して、実はやりたかったのは符号化ではなく、下の本の最初の「帽子の問題」。
問題は、前向き/後向きバラバラに帽子を被った人たちが一列に並んでいる状況で、整理員が指示を出して全員の帽子を同じ方向になる様にする、というもの。指示は「○番から×番の人」のように範囲で指定できます。なるべく少ない回数でそれを達成するにはどうしたらよいか、というわけです。
パッとみただけで「あ、これランレングスみたいなのして偶奇で判定だ」とは閃いたので、本は読まずに見切り発車始めてしまったのですが、ここで、はて、ランレングスってどう書くのがエレガントかなー、と脱線し始め、そちらの迷宮にハマってしまった、というパターンですかっこわるー(実際この本でも迂回しながらランレングス圧縮にランディングしてます。合わせてLZのような話も出ていました)。一般のランレングスの場合、処理対象はあらゆる記号、かつ、出るタイミングはランダムですが、この問題では前向き(F), 後向き(B)が必ず交互に出流ので、もっと簡単にできそうです。そこまでやらんけどなー。
まずはナイーブに…
ベースラインとして、まずは単純極まりない、Cで書いたらこうなる、みたいなのを書く、がセオリーだと思うのですが、そこは脊髄反射プログラマの私なので、最初に考えついた方法で猪突実装してしまいました。内容は 1 runを一気に消したい→lstripで最初の文字を剥がしちゃえ、でした。
def rle_strip(s): while s: c = s[0] striped = s.lstrip(c) yield((c, len(s) - len(striped))) s = striped
lstrip()で剥がして、元の長さから剥いだ後の長さを引いて差を出していく、という単純ながらも、あれ、もうこれで良くね? なアルゴリズムに見えます。ジェネレータイテレータとして実装したので、一個剥がすたびにyieldで次を返しています。
ついでなので単純極まりないほうも作っておきましょう(これが後からガビーンを産むことになるのですが…)
def rle_naive(s): prev = s[0] cnt = 1 for c in s: if prev != c: yield((prev, cnt)) cnt = 1 else: cnt += 1 prev = c yield((prev,cnt))
同じようにジェネレータイテレータとして実装しておきます。
pythonicな、あるいは numpy的な解法
python的、というより関数言語的というかリスト処理的というか、並列にできるもんはリストで並べてしまう戦略*1。
numpy使うなら結構簡単でずらしたndarray同士で比較した ndarray作って、nonzero()またはwhere()で場所を拾う、というよくある戦略で良いです。
def rle_numpy(s): o = _succ(s[-1]) # sentinel s = np.array(list(s+o)) idxs = np.append(-1, np.nonzero(s[1:] != s[:-1])[0]) return zip(s[idxs+1], idxs[1:] - idxs[:-1])
pythonicな、あるいはリスト内包な解法
上記numpy方式をリスト内包でできないかなーとやってみたのが次。僕のリスト内包の作り方って基本的に後ろから、「まずこれ作ってー、作ったやつでこうしてー」と思考の順番に前につなげて作ってしまう、、、
>>> list((lambda t: zip(t[1:],t))("good speed")) [('o', 'g'), ('o', 'o'), ('d', 'o'), (' ', 'd'), ('s', ' '), ('p', 's'), ('e', 'p'), ('e', 'e'), ('d', 'e')] >>> list((lambda t: (a!=b for a,b in zip(t[1:],t)))("good speed")) [True, False, True, True, True, True, True, False, True] >>> list((lambda t: compress(range(len(t)), (a!=b for a,b in zip(t[1:],t))))("good speed")) [0, 2, 3, 4, 5, 6, 8]
という癖があるので、いつも最終的に凶悪なのが生まれてしまいます…
(lambda s:(lambda a:[(s[q],p-q) for p,q in zip(a,[0]+a)])(list((lambda t:compress(range(len(t)),(a!=b for a,b in zip(t[1:],t)))) (s[0]+s+chr(ord(s[-1])+1)))))("iiinnnputtt")
— 焼けてきたtkuro11 (@tkuro11) 2022年1月29日
[('i', 3), ('n', 3), ('p', 1), ('u', 1), ('t', 3)]
はい産まれましたーーーー(ムスカ大佐の目が見えなくなってしまうレベル)。
まあ清書して、
from itertools import compress def rle_wierd(s): o = _succ(s[-1]) # sentinel return [(s[q],p-q) for p,q in _pairwise(compress(range(len(s)+1), (a!=b for a,b in _pairwise(s+o,s[0]))) )]
とはしたものの、numpy使わない代わりにitertools.compressは使うは、pairwiseは実は無くなっていたことに気が付かず、自前で作ることになるはでもうダメダメwww
あ、この辺で使っていた_pairwise, とか_succは以下です。
## utility routine ## (A, B, C, ..., Y, Z) -> ((0, A), (A,B), (B,C), ..., (Y,Z)) def _pairwise(seq, last = 0): for c in seq: yield(c, last) last = c # Next character in ASCII def _succ(c): return chr((ord(c)+1) % 255)
いやー盛大に自爆!
しかもー
ベンチとってみて氏ぬ。M1 Macbook Airでやってみました。
tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % sysctl machdep.cpu.brand_string machdep.cpu.brand_string: Apple M1 tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./runlength_test.py ***** --- run-length 1 (totally random) --- ***** # rle_naive 0.724449584 # rle_strip 2.3304234999999998 # rle_numpy 2.630215708 # rle_wierd 1.5978349170000001 ----------- ***** --- run-length 10 aaaa bbbb --- ***** # rle_naive 0.33949912500000057 # rle_strip 0.2601713329999997 # rle_numpy 1.0721955419999993 # rle_wierd 0.8074890840000002 ----------- ***** --- run-length 100 aaaa bbbb --- ***** # rle_naive 0.2919787500000002 # rle_strip 0.05756099999999975 # rle_numpy 0.930163125 # rle_wierd 0.7280477919999999 ***** --- run-length natural language --- ***** # rle_naive 0.4841780419999999 # rle_strip 2.0906731670000003 # rle_numpy 1.9265417080000002 # rle_wierd 1.1903997910000008
なななななななななんと、numpyが一番遅い!!!!
しかもnaiveが一番まともじゃないですか。stripはrunが長くなってくるとゲキ強いですが、それにしても何の工夫もしてない奴が一番早くって、一番苦労したwierdがあんまり報われないとか、これはひどいなー。絶倫にアウトじゃないですか。
まあでもやっていることを考えるとそれはそうか、という気もしますね。2リストを全部見ていくよりも1リスト1イテレーションの方が軽いですね。
encoder & decoder
とりあえず目的はこれじゃないんだけど、一応遊んでみるために書いておきました。-nで最小ラン長を指定できる様にしておいた。
encoder
from runlength_test import rle_naive import argparse parser = argparse.ArgumentParser() parser.add_argument('-n', '--num', action="store", dest="num", default=1, type=int) parser.add_argument('filename', type=str, nargs="?") args = parser.parse_args() n = args.num if args.filename: f = open(args.filename) else: import sys f = sys.stdin code = rle_naive(f.read()) ret = "" for c, l in code: if l >= n: ret += str(c) * n ret += chr(l-n) else: ret += c * l print(ret)
decoder
from runlength_test import rle_naive import argparse parser = argparse.ArgumentParser() parser.add_argument('-n', '--num', action="store", dest="num", default=1, type=int) parser.add_argument('filename', type=str, nargs="?") args = parser.parse_args() if args.filename: f = open(args.filename) else: import sys f = sys.stdin text = f.read() cnt = 0 last = ret = "" for c in text: if cnt >= args.num: ret += last * ord(c) cnt = 0 else: ret += c if last != c: cnt = 0 cnt += 1 last = c print(ret)
Alice in worderlandのrabitholeのところを拾ってきて圧縮?してみた
tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt > alice_n1.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt -n2 > alice_n2.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ./encoder.py alice_down_the_rabithole.txt -n3 > alice_n3.comp tkuro@carnalite ~/00PlayGround/5265da25fd296305141db600c27095d4 % ls -l alice_* -rw-r--r-- 1 tkuro staff 11725 2 3 00:12 alice_down_the_rabithole.txt -rw-r--r-- 1 tkuro staff 22383 2 3 01:00 alice_n1.comp -rw-r--r-- 1 tkuro staff 11867 2 3 01:00 alice_n2.comp -rw-r--r-- 1 tkuro staff 11658 2 3 01:01 alice_n3.comp
あーやっぱりランをある程度伸ばさないと普通のテキストは難しいですねー。3でやっと元ファイルより小さくなった。
SRLEとかLZとか、ちょっと面倒なので今回はパス。
教訓
- numpy的な書き方は楽しいけど、いらんことをいらんふうにやってしまうと、素朴なアルゴリズムの方が素朴なだけに速いことが多い
- リスト内包表現は楽しいけど、(ry
- 案外最初のひらめきが良かったりする
- ランレングスは普通の文章には難しいややっぱ
我ながらしょうもないことばかりやっているなあ、と思いました。
今回のはここに置いておきました。
runlength_test.py · GitHub
*1:こういうのなんていうんだろう
SICM読み始め
SICMを読み始める
いつの間にか時は経ち、その資格があるとも思えないのにも関わらず人に教える立場に立ち位置が変わってしまいました。情報系統の場所に入ったんだけど、そのうちに「人間を中心に考える」という全国でも珍しい名前の学科にスライド。さらに、そんなこんなしているうちにその立ち位置までズリっと横に移動して、あれよといううちに機械工学に絡んでしまいそうなところまで滑走中です。さてなどうしよう。ラグランジアンとかハミルトニアンとか何となくの等式しか覚えてないよどうしよう。
と悩んでたらふと、SICPのサスマンさんの魔術的本 SICM(Structure and Interpretation of Classical Mechanics)のことを思い出しました。SICPは丁寧に読んだら非常に読みやすかったので、きっと僕には波長が合うんですね。SICMを丁寧に読んでみよう!
Structure and Interpretation of Classical Mechanics (The MIT Press)
- 作者:Gerald Jay Sussman,Jack Wisdom
- 出版社/メーカー: The MIT Press
- 発売日: 2015/02/06
- メディア: ハードカバー
しかし買うのしんどいなーと思っていたら、大学の図書館にあったので早速借りてきた。よーし読むぞー。読むぞー。。。。。長いよー。
そうだどっかにメモ程度に書き加えていけばきっと辞めないはず。と信じて描いてみることにしました。明日から。。。いつまで続くかなー
Request, replyパターン
途中途中で更新していく。
前回のhello <-> world なパターンは絵にするとこんな感じ。最も単純かつよく使う Request/Reply パターンと呼ぶそうな。
その前に、衝撃を受けたので書いとく
- zmq_ctx_new()で生成したコンテキストはスレッドセーフ
- zmq_socket()で作ったソケットはスレッドアンセーフ
REQタイプ
本の説明はいきなり last-peer とか fair queue とか出てきて混乱したんだけど、実は単純な話で zmq ではソケットタイプによって使用方法にある程度縛りを設けて、通信をパターン化しているらしい。、rfc読んだら一発だった。
https://rfc.zeromq.org/spec:28/REQREP/
ZMQ_REQタイプはlock-step round-robin algorithmでリクエスト送信、そのリプライの受信を行う。クライアント側。単純なモデルで信頼性はそれほど必要としない、という前提。
- 任意数のREP or ROUTER に接続できる。
- 一度に1メッセージずつ送信-> 返信するモデル
送信パケットは
- 空フレームがデリミタとして追加される(? まだいまいちイメージできてないがダムフレームで送るのかな)
- 1つ以上のデータフレームでメッセージが構成される
- 相手がいないとかで送信できないときは、ブロックするかエラーを返す
- 送信できなかったメッセージも破棄されない
返信パケットは
- last-peer(つまりREQを送ったやつ)から到着したメッセージのみ受理
- それ以外のhostからのメッセージはしれっと捨てる
ZMQ_REP はいわゆるfair queue。つまり小さいほうから詰め込んでいく考え方。WFQじゃないのか。
REPタイプ
REQの受け側。リクエスト受信、そのリプライの送信を行う。
- 任意個のREQ or DEALER ピアに接続できる
- メッセージをフィルタや改変しない
- 一度に1メッセージずつ
受信(リクエスト)パケットは
- アドレスエンベロープは0以上のフレームからなりそれぞれが1つの識別子を持つ
- 空フレームがデリミタ
- 1つ以上のデータフレームでメッセージが構成される
受信パケットは
- fair-queueingで到着メッセージを受信
- アドレスエンベロープとかデリミタは削除してくれる
- アプリケーションには残りの実データが送られる
返信パケットは
- アプリケーションからの呼び出されて指定されるのを待つ
- アドレスエンベロープやらデリミタが追加される
- 発信元に送り返される
- 発信元が死んでいたりしたら、しれっと捨てるか、エラーを返す。
ついでなのでROUTER
REPの非同期版。DEALERクライアントとお話しするサーバのベースになることが多い。
明示的にアドレス使って、複数のピアと通信できる。
- 任意個のREQ, DEALER, ROUTERと接続できる
- 接続したピアに対して 1つのダブルキューを管理する
うーむ、ダブルキューてなに?
あー、理解。送信・受信、両方向キューですね。
- 自発的に送信するときも、リクエストもらうときも ダブルキューを確保する。
- 送信キューは接続がなくても破棄されない
- 受信キューは接続が切れたら破棄。
- 一意の "identity" binary string(?)とやらで各ダブルキューを選択
- Identity metadata property(?)とやらでピアが名乗る(識別される)ことが可能(なんのこっちゃい)
- 送受信キューサイズは実行時にリミットを与えられる
受信メッセージは
- fair queueing
- 到着メッセージは発信元ダブルキューの識別子が入ったフレームが最初に入る
送信メッセージは
- 送信メッセージの最初のフレームを破棄してこれをダブルキューの識別子とする- 送信キューに空きがあればそこに入れる
- キューがない、または空きがなければ、しれっと捨てるかエラー(設定による)
- ブロックしない
さらについでなのでDEALER
ØMQを復習
- この名前よく聞くがよく理解もしていない
- ChangeLogを見ると2013年にやっていたらしい。例によって。
- jupyter notebook でも使われているらしい
というわけでちゃんと理解しなおしてみようといつものごとくsafaribooksを立ち上げて見た。
使う本はこちら
https://www.safaribooksonline.com/library/view/zeromq/9781782161042/
スタート
we are living in a connected world だそうな。low-levelでは面倒だが、high-levelではスピードが得られにくい。ちょうど中間が欲しい。そればzmqなのさ、という話。savior (救世主)
とか書いてある。ケンシロウめ。
メッセージキューの話
FIFO queue のこと。priority queue てなんだっけ。あれか、レジカウンターでは時間かかる人を後回しにしたほうが平均待ち時間がってやつ。
キューは大規模な分散システムを実現するためのキーファクターだって書いてある。さらに非同期通信(AIO)。リアルタイムでは必須。シングルスレッド上に複数のタスクをマップできる。JavaScriptっぽい。
よくある例としてWebappの話が次に続く。多量のアクセスに対して、シングルスレッドでは捌き切れず、マルチスレッドではDDoSされるとスレッド爆発してしまう。メッセージキューによるAIOならば(キューマシンを分ければ)これらの問題とともに対故障性にもすぐれるとか。
んでZeroMQ
このメッセージキューを実現する仕組みZeroMQ.sockets on steroids.
分散/平行アプリケーションのためのメッセージングライブラリ.
- 単純さ
- 性能
- Brokerlessデザイン
中央集権でないらしい。(という事は対故障生の話は嘘なんでは…)
というわけで 僕らの友達 HelloWorld
サーバ側:
zmqでは全てはコンテキストから生成されるので、まずはこれを作ってソケットを生成する。
まずは準備して、
#include <zmq.h> int main(int arc, char const *argv[]) { void* context = zmq_ctx_new(); void* respond = zmq_socket(context, ZMQ_REP);
ソケットにアドレスをバインドして、
zmq_bind(respond, "tcp://*:4040"); printf("Starting waiting...\n");
メッセージループに。
for (;;) { wait_for_hello(respond); printf("Received: hello\n"); sleep(1); send_world(respond); printf("send: world\n"); }
終わったら(終わらないけど)後始末。
zmq_close(respond); zmq_ctx_destroy(context); return 0; }
んで肝心の受信の方はこんな感じになる(ちゃんと"hello"か確認してないだろう、というツッコミはちと置いておいて)
void wait_for_hello(void* respond) { zmq_msg_t request; zmq_msg_init(&request); zmq_msg_recv(&request, respond, 0); zmq_msg_close(&request); }
単純にメッセージを作って、ソケットからrecvするだけ。んで終わったらメッセージは捨てる。
んで送信。
void send_world(void* respond) { zmq_msg_t reply; zmq_msg_init_size(&reply, strlen("world")); memcpy(zmq_msg_data(&reply), "world", 5); zmq_msg_send(&reply, respond, 0); zmq_msg_close(&reply); }
同じように、基本的にメッセージを作ってソケットに投げつけるイメージ。メンバ変数というかメッセージのバッファを指定してmemcpyすんのがちとめんどいがそれはCだから
基本こんだけ。
https://github.com/tkuro11/zmqtutorial
まとめ
zmqはソケットを直に使うよりは相当に楽に非同期メッセージキューを実現するライブラリで、基本的に高レベルな操作を使ってかけるが、考え方はこれまでのモデルと大差ないので覚えやすい。ソケットの種類がすごいいっぱいあるけど、これはマルチキャストとかの対Nに対応しているから、といったところかなー。まだぼんやりしている。
次回はその機能てんこ盛りなソケットタイプから request reply の仕組みあたりかな。
Rust入門
同僚の人に「Rustっておもしろい?」と聞かれて気になったので、ここやってみる。
https://rust-lang-ja.github.io/the-rust-programming-language-ja/1.6/book/
しかしだ。twitter検索してみたら
2012年02月06日(月)
Rustのclosureって全然closureじゃない気がするんだけど。upvarアクセスそのままでは出来ないようだし。どこがpythonと違うのよ。これは単に僕の理解が足りないだけ?
posted at 18:56:23 削除
2月6日@tkuro11
Rust, 流石に type str=int とかは単に無視かw。Naggingかよ。せめて怒ってよw
posted at 18:04:55 削除
2012年02月01日(水)2 tweetssource
2月1日@tkuro11
Rust, writer_utilとかナニモノ
posted at 16:54:06 削除
2月1日@tkuro11
焼けてきたtkuro11@tkuro11合成と一致検証の合間にRustコンパイルするなど。
posted at 16:26:48 削除
5年も前にやってたらしく、完全に忘れている自分に旋律戦慄などした。
環境構築
まずはインストール。
流行りのshellダイレクトインストール(と僕が勝手に呼んでいる)方法がサポートされているようで精神衛生上よろしいのでこれにする。
% curl -sSF https://sh.rustup.rs | sh
なんでこれが好きかというとこれって覚えやすいのでどこに行っても使えるから、です。
これで rustc とか cargo(ビルドシステム)がインストールされる。
% source ~/.cargo/env
するとパスとかの環境変数設定が完了。いや、とかじゃなくて中身見てみると本当にパスの設定しかしていないw
さらにvim用の環境をこさえる。ここを参考にした。
http://qiita.com/hinagishi/items/f43538ce8120e483077e
cargo install --git 'https://github.com/phildawes/racer.git' cargo install --git https://github.com/rust-lang-nursery/rustfmt
結構時間かかる。racerは補完のため。rustfmtは自動整形のため。
わあ楽チンと思ったのもつかの間。rustfmtの方でみょーなエラーにひっかかる
error[E0554]: #[feature] may not be used on the stable release channel --> /home/tkuro/.cargo/git/checkouts/rustfmt-5390e0ead582d971/a1fd68d/src/lib.rs:11:1 | 11 | #![feature(rustc_private)] | ^^^^^^^^^^^^^^^^^^^^^^^^^^
よくわかんないけど、nightly buildじゃないとアカンということかな。というわけでrustupでコンパイラを入れ替える。
% rustup install nightly % rustup default nightly
rust version 1.22.0-nightly (368122087 2017-09-06)になった。
あ、よく考えたらnightlyまでいかんでもbetaでいいのか・・・
以下でも行けるみたいだけど overrideって何を上書きするんだろう。あとで調べよう
% rustup override set nightly
とりあえずこれでコード補完とシンタックスハイライト、自動整形までおk
その他気になるもの
Compiling aho-corasick v0.6.3
なんだろうこれ
コード書く
までもなく cargoで自動生成するとテンプレートが生成される。
% cargo new --bin hero_world % cd hero_world % cargo run Compiling hero_world v0.1.0 (file:///home/tkuro/Rust/hero_world) Finished dev [unoptimized + debuginfo] target(s) in 0.31 secs Running `target/debug/hero_world` Hello, world! % cat src/main.rs fn main() { println!("Hello, world!"); }
全然前のこと思い出せないけど、あまりきれいな言語じゃないなー。!は関数じゃなく
マクロなんだそうな。
cargoの作ってくれるテンプレートは プロジェクトルートに src/があってこの中の
main.rsがエントリポイント(おそらくルートのCargo.tomlで変えられるんだろう)。
cargo build とか runとかすると target/debugとかにバイナリが生成される。
生成物でかい
swordfish% ls -l target/debug/hero_world -rwxr-xr-x 2 tkuro tkuro 3885344 9月 8 07:45 target/debug/hero_world*
言語にダイブするのは次のエントリで。
まとめ
- 結構簡単に環境が構築できる
- rustupのおかげで環境の管理が簡単
- cargoがモダンな感じに開発をサポートしてくれる。
- 言語はどうも省略形が多いが、アノテーションとか#で簡単そう
[haskell] twice twice twice
> twice twice succ 0 4 > twice twice twice succ 0 16
でビビったり。とかなさけない。
しばらくいじってなかったらだいぶ感覚鈍っていて、というか以前やった時もあんまり理解できていなかったんだなと少し反省を重ねつつも、全く成長しない自分に相変わらずの嫌悪感を持つふりをしながらも、結局は自分に甘いじじい青二才。
だなーと思いながら、 twice を重ねた時の挙動をやっとこさ理解できたのでメモ。
定義から
twice f x = f (f x)
ということはカリーな感じで
twice f = \x -> f (f x)
2つならどーだ
twice twice ==> \f -> twice (twice f) ==> \f -> (\x -> (twice f) ((twice f) x)) ==> \f -> (\x -> (\y -> (f (f y)) ((\y -> (f (f y))) x) )) ==> \f -> (\x -> (\y -> (f (f y)) (f (f x)))) ==> \f -> (\x -> (f (f (f (f x)))) )
あーなるほど。
本番
twice twice twice ==> \f -> (\x -> (f (f (f (f x)))) ) twice ==> \x -> (twice (twice (twice (twice x))))
ぎゃー。しかし twice ( twice x ) が上の通りであることを考えれば
==> \x -> \f -> { (f (f (f (f x))))) } が4段分
で結局 16となるわけか。
概念としては
((twice twice) twice) succ)
とゆーのは素直に 「二回(二回を(二回分 ( succ))) する」でよいわけか。
んでとどのつまり 2^2^2と考えればよいわけですね。
じゃあtripleなら
3^3^3になるのかな、と思ったけど7,625,597,484,987だからだめだーと
> triple f x = f ( f( f x)) > triple succ 0 3 > triple triple succ 0 27
3^3で日和ってみた。あと (3^3)^3とか
> triple (triple triple) succ 0 19683
ちょうどひっくり返るのかひっくり返らない。そのまま!いややっぱりひっくり返る!ww(アホか僕) おもしろい。
他人のワーク
先に文献レビューをするのがアカデミックなのでしょうが、ダメ人間なので後から探したりなど。
http://spivey.oriel.ox.ac.uk/corner/Twice_twice_twice
まんまのがあった。しかも処理系にpretty printさせてるのでカッケー
駄菓子菓子、Haskellの関数適用は左結合だから
reduce (Ap (Ap Twice f) x) = return (Ap f (Ap f x))
これはおかしいんじゃないだろうか?これだと 後ろのTwiceが先に評価されない?
余談ですが
Tonight, Tonight, Tonight はけっこー好きです。
追記:
ややこしいことしてたけど、
twice f = f.f
とすれば思っきし自明。悩む価値もなかったりなんぞした。
twice twice f ==> (twice . twice) f ==> twice ( f.f ) = (f.f).(f.f) twice twice twice f ==> (twice twice twice) f { ( twice twice f ) = f.f.f.fより } ==> (twice.twice.twice.twice) f ==> (twice.twice.twice (f . f)) ==> (twice.twice (f.f) . (f.f)) ==> (twice (f.f).(f.f) . (f.f).(f.f)) ==> ((f.f).(f.f).(f.f).(f.f) . (f.f).(f.f).(f.f).(f.f))