Map の代数的構造と差分によるプログラミング
-
- いいね！1
Yuta Okamoto
@okapies
@pokarim ありがとうございます。Map の差分計算のあたりは CRDT の話を思い出しました。 qiita.com/everpeace/item…
2017-10-04 01:34:10
pokarim
@pokarim
@okapies もっとずっと単純な話ですが、こじつければ関係性がなくもないですね。差分というのは Operation-Based の操作にあたるものを、単純なデータ構造同士の演算として考えようということなので、たとえば差分の合成が可換であれば操作が可換ということになりますね。
2017-10-04 01:50:25
pokarim
@pokarim
@okapies React の話はユーザーが State-Based なイメージで書いたコードが自動的に Operation-based な処理に変換されると楽になる場合がある、と言い換えられるかもしれません。
2017-10-04 02:02:49
Yuta Okamoto
@okapies
@pokarim なるほど。あと、reactive programming においてデータが可変か不変かは関係がないという話は、Akka Streams が、データフローグラフを最終的にアクター（＝状態を持つ）のネットワークに変換して実行する話を連想しましたが、合ってるかはちょっと分からないですw
2017-10-04 02:10:53
Yuta Okamoto
@okapies
@pokarim というか、おそらく逆の話をされているのですかね。状態の演算として書いたものがイベントベースの処理に変換されるような。
2017-10-04 02:12:13
pokarim
@pokarim
@gakuzzzz はい。Map[A, B] がモノイドになるためには、Map インスタンスがデフォルト値を持たなくても B に Monoid 制約があるだけで十分です。単位元を暗黙的なデフォルト値とすればよいので。しかし例えば環にする時は、加法と乗法の単位元が別なので必要になってきます。
2017-10-04 08:36:26
pokarim
@pokarim
たとえば Int の乗法の単位元はデフォルト値が 1 で空の Map になります。集合の積(共通部分)の単位元はデフォルト値が true になりこれは A の全体集合に相当します。 twitter.com/pokarim/status…
2017-10-04 08:48:51
pokarim
@pokarim
デフォルト値をもつ Map 同士の演算はデフォルト値同士の演算も伴い、Set[A] を Map[A, Boolean] とすれば例えば補集合も表現できます。その他乗法が定義されない場合でも、デフォルト値を持つ空の Map は定数関数に相当するものなので一般的に便利です。
2017-10-04 08:53:52
pokarim
@pokarim
Map[A, Boolean] が Set[A] と同等とみなせるというのは、その Map が指示関数になってるということで、そもそも Map は外延的にあたえられた関数そのものなので、Map を内包的な関数であるところのラムダ式におきかえても同じ演算が定義はできます。
2017-10-04 10:41:28
pokarim
@pokarim
ただ、ラムダ式のようなかたちで与えられた関数同士の演算を行うと、演算の度に入れ子が深くなってしまうので計算効率が落ちたりするので、実際は同じように扱うわけにはいきません。
2017-10-04 10:44:39
pokarim
@pokarim
まえにもしてました。 twitter.com/pokarim/status… twitter.com/pokarim/status… twitter.com/pokarim/status… twitter.com/pokarim/status…
2017-10-04 10:54:06
pokarim
@pokarim
関数というのは一見万能なようでいて実は不便な点もあって、引数を渡して評価するという操作しか用意されていないので、関数から関数への変換という形で記述できるものは案外限られている。
2016-12-28 14:11:41
pokarim
@pokarim
たとえばパーサコンビネータなどでモナドの合成をする際に、その中身を解析しつつ合成するということはほぼできない。Arrow であれば関数とメタデータ的なものをセットにしておけるのでそういった制約から逃れられる、といったことをどこかで読んだけど出典を忘れてしまった。
2016-12-28 14:14:06
pokarim
@pokarim
状態遷移を関数ではなくデータとして表現しておくと、状態遷移から別の状態遷移への変換といったものが定義しやすくなるとかそんな感じのことです。
2016-12-28 14:21:21
pokarim
@pokarim
View の materialize や関数のメモ化は内包的なものを外延的な表現に移し替えることだと考えることができるけれども、それと同じように状態遷移を手続きや関数ではなくデータの差分として捉えるというのも、状態遷移を外延的に捉え直すということだと言える。
2016-12-28 13:57:45
pokarim
@pokarim
関数というのは一見万能なようでいて実は不便な点もあって、引数を渡して評価するという操作しか用意されていないので、関数から関数への変換という形で記述できるものは案外限られている。
2016-12-28 14:11:41
pokarim
@pokarim
View の materialize や関数のメモ化は内包的なものを外延的な表現に移し替えることだと考えることができるけれども、それと同じように状態遷移を手続きや関数ではなくデータの差分として捉えるというのも、状態遷移を外延的に捉え直すということだと言える。
2016-12-28 13:57:45
pokarim
@pokarim
状態遷移を関数ではなくデータとして表現しておくと、状態遷移から別の状態遷移への変換といったものが定義しやすくなるとかそんな感じのことです。
2016-12-28 14:21:21
pokarim
@pokarim
たとえばパーサコンビネータなどでモナドの合成をする際に、その中身を解析しつつ合成するということはほぼできない。Arrow であれば関数とメタデータ的なものをセットにしておけるのでそういった制約から逃れられる、といったことをどこかで読んだけど出典を忘れてしまった。
2016-12-28 14:14:06
pokarim
@pokarim
@pokarim 受理する文字列の先頭（一文字目）の集合を、コンビネータが付加的なデータとして持つとか、そんな感じだったように覚えている。
2016-12-28 14:19:12