#これがなにになるかわからないのですが、逆に、0in,n-outの辞書も定義できるわけで。
#概念的には、0-in,1-outとはすなわち、コレクションに相当することになります。これまでの観察から、手続きの形式にはそれに対応するデータ構造があるように思えます。0-in,1-out(thunk)にはコレクションフレームワークが対応、1-in,0-outの手続きには集合が対応、1-in,1-outの関数にはhash-table(とその仲間)が対応する。そして、n-in,m-outの関数に対応するようなデータ構造はなにかということを、くだくだと考えていたのでした。
#コレクションは集合ですよ (重複要素が許されているかどうか、などの詳細はありますが、「値を単に集めたもの」がコレクションでして、集合と別扱いする意味はありません)。そんで、関数＝集合から集合への写像、ですから、集合そのものを関数と同一視するのはちとトリッキーです。
#ゼロ引数のthunkは、純粋な関数ならば常に同じ値を返すしかないので、定数と同じことになります。一方、副作用のある世界でのthunkは、値域集合からその都度ひとつの値を選んで返してくる、「サンプリング」を行う関数とみなすことはできます。引き渡される値がサンプリングされたものである、ということを心得ている限りでは、thunkと集合を一緒に考えることはできるかもしれません。(もっとも、集合自体は「どのような基準でサンプリングされるか」という情報を持っていないので、完全に同一視してしまうことはできないでしょう)
#ちょっと言葉がたりなかったです。いまいる世界「Gauche」は副作用のある世界です。thunkをあたえられたなら、それをイテレータとしたコレクションが対応する。1引数で戻り値がない手続きがあったならその値域を決める集合が決まる。1引数で返り値が1つの手続きが与えられたなら、それを使ってlazyにhashを生成できる。(すなわちメモ化。)
#うまい表現をもたないのですが、副作用のある世界の手続きは、写像とはことなる存在のように思えます。generatorなどがそうです。
#(1in,0outで集合をどう決めるのかについては、未消化なところがあります。)
#thunkを「メモ化」する過程が、すなわちコレクションのイテレートになります。
#戻り値が無い手続きなら値域は空集合なのでは?
#そうでした。定義域です。
#戻り値のない手続きから、定義域を生成する・・・・そういうことが可能なのかしらんとか。
#あと1-in 1-outの手続きとhashが対応するのは副作用が無い場合だけなので、何か前提が混ざっちゃってるような。
#あ、
#なるほど。
#もちろん、呼ばれる度に違う値が返るthunkは写像とは言えません(と、上で書いています。) だけれども、その一回毎のを値域からのサンプリングと考えることはできるよ、ということです。あるいは、暗黙の引数と戻り値として「世界の状態」が渡されている、と見ることもできますが。
#副作用を前提にしているなら、その副作用の歴史を記録する手段があって、thunkの副作用を記録する形式がコレクション、1-in,0-outの手続きの副作用を記録するのが集合(これは無理があるか・・・)、1-in,1-outの手続きの副作用を記録するのがhash(メモ化)。
#thunkをサンプリングと考えた場合、そのサンプリングに一定のルールがあるはずで、そのルールをコレクションは持っていません。例えば「2つのサイコロの目の和」を返すthunkと、「2～12までの整数のコレクション」は同一視できないわけで。(まあこの場合、重複を許す集合なら頻度を反映できるけど… 直前の状態に次の返り値が依存する場合は単なるコレクションじゃなくて状態機械とみなさないとだめっすね。)
#ああ、でも、thunkが与えられて、その返り値の系列から、何らかのモデル(マルコフ過程とか)を仮定してデータソースの近似を得る、みたいな用途はあるから、そのへんの話とつながらなくはないかな…
#話がもどりますけれど、集合は要素が重複しないものだと学部で叩きこまれたので、情報系の重複を許す「集合」はトリッキーな気もします。(もっとも、むずかしい数学の話になるとさっぱりわからないので、先端の解釈は不明です。)
#なので、集合と「集まり」を区別する、と。集合をキーにして、「集まり」の要素を関連付けたのがhash。関連付けがないものが、集合、「集まり」(連想リストの要素の、cons の carとcdrに対応します。)
#この解釈にたてば、集合は値のない辞書で、「集まり」はキーのない辞書とみなせる・・・・・のか？とか
#実装の話になると、さらに弱いのですが、集合は列挙するのではなく木を歩くのではないか？とか考えるなら、辞書のケースとみなすと自然かな。と
#これをどんどん推し進めたさきに、(なぞの)多値の辞書という概念が。
#区別したければ、重複を許すコレクションをBag、許さないコレクションをSetと呼ぶことはありますね。でも要は、所与の問題を扱うのに都合の良いように定義すればいいので、問題がはっきりしないのに定義にこだわっても仕方ない気が。
#辞書を Set -> Bag とみなして、さらに値域あるいは定義域が空の場合を考えるってことですね。それはそれで理屈が通ってますね。しかし φ -> Bag に対応するthunkは作れますが、全てのthunkが φ -> Bag で表せるわけではないので、やっぱり手続きと綺麗に対応づけるのは難しいな。
#あと、多値は数学的に考えるなら単なる直積で、例えば2値を返す辞書って考えても Set -> Bag × Bag みたいにしかならないので、それなら「タプルでいいじゃん?」と思っちゃうんだけどどうかしらん。
#インターフェースの見た目から言えば、入力要素にn個あたえて、等価判定をm個用意したとすると、先頭のm個がSet(キー)となり、残りがBag(値)になる。
#先頭のm個については、trieと同じようなprefixが考えられる。同じprefixの「辞書」を定義できる、と。
#lset-*が等価判定を用意しているように、一つの入力に一つの等価判定を用意しているケースが集合。
#等価判定を用意しなかったら、Bagということになる。
#等価判定ではなく、整列を定義するような関数をあたえたなら、Sorted*のようなもの？ができるか？とか。
#a:Set × b:Set × c:Set -> Bag から a:Set -> (b:Set × c:Set) -> Bag をくくりだす、みたいな操作ですよね。でも理屈の上では先頭を特別扱いする必然性は無くて、 b:Set -> (a:Set × c:Set) -> Bag みたいな分解だってできるわけで… 話としては、 a:Set × b:Set -> Bag から a:Set -> b:Set -> Bag にするオペレータを用意しとくから、それに都合の良いように使う人が順番を決めてね、っていうことになるのかな。
#先頭を特別扱いしたのがcurry化なのではないかとか。
#ああ、あとそういうインタフェースにしたとして、同じキーで異なる値になってるデータが与えられた場合はどうなるんでしょ。というのは φ -> Bag な構造と統一しようとしたらそういうのを扱わざるを得ないですよね。
#まず、キーの並びかたには意味があるわけで、これは万能アクセサの参照列(~ obj 'hoge 'foo 'bar)のようなものです。
#その意味で、万能アクセサと関数の部分適用は近いそんざいな印象を受けています。
#辞書のキーが複数になったなら、同じようなことが考えられるはず。(辞書式順序といいますか。)
#並びには意味がありますが、並びの中でどれが優先されるか、というのは別の話で、先頭が常に優先される (先頭から木構造になってる)とアプリオリに決まってるわけじゃないでしょう。関係モデルとか、順序に意味があるけど優先度はありませんよね。
#いや、木構造を導入してもいいんですが、それは本来の性質としてあるものじゃなくて「そう決めると都合が良いのでそうしました」ってことになると思うんですよ。だとしたらその「都合の良さ」が何なのかが示されてるといいなと。
#話の流れを読まずに投下。英語版(しかチェックしてない)の11.7章DBIでdbi-make-connectionのoption-alistがまちまちになってます。(options-alistとかoptons-alistとか)。
#直しました。まはろ＞Kei
#(make-duck-dict 'eq)でdをつくったとすると、(put-duck-dict d k v)はhashを生成する。(put-duck-dict d k)は集合を生成する。
#(make-duck-dict)でdをつくったならば、dはコレクションとなる。(put-duck-dict d v),(put-duck-dict d v w)<---多値のコレクション
#ここで、多値のコレクションとしたものと、いまのhashをくらべると、現在のdict-fold,dict-mapはkがキーだとか関係がないわけです。
#さて、(make-duck-dict 'eq 'eqv)でdをつくったとして、(put-duck-dict d k)したなら、それはkに(make-duck-dict 'eqv)を割り当てることを意味します。
#これで、自然にn-inのdictha
#n-inの辞書は導入される。これが順序に意味があるという理由です。
#ダックタイプで集合、ハッシュ、コレクションを扱おうという視点です。
#関係モデルのタプルとなにか関係があるような気がするのですが、いかんせん不勉強なもので・・・・
#問題点としては、(make-duck-dict 'eq)で生成したdに対して、(put-duck-dict d k v),(put-duck-dict d k)のように、集合とハッシュが混在したような代物もできるということでしょうか。
#利点としては、n-in,m-outの手続きのメモ化を自然にかけるように思います。(f x y z)--->(values a b c) なら($ apply put-duck-dict d x y z $* values->list $ f x y z)
#dはfのアリティをしらべて、適切に生成します。
#argをリストとしてまとめてequal?するのではなく、x y zに異なる等価判定を設定することができます。
#n-in, m-outの辞書を導入する問題意識をあまり理解できていないので、的を外しているかもしれませんが、それって普通のhash-tableではだめなんでしょうか?
#($ values $ hash-table-put! d k $ values->list $ f x y z)
#hash-table-put!の戻り値がvalueであることを仮定しちゃってますけど
#x y zごとに異なる等価判定を持たせたいなら、make-hash-tableで
equal?とhash手続きを渡せるようにすればいいだけじゃないかと思います。
#単に n個の要素を持つlistがキーで、m個の要素を持つlistが値の辞書だとうれしくない局面があるんでしょうか?
#なるほど＞yamasushiさん。等価性判定関数の数で任意個のキーを持たせられるってアイディアは確かに面白いです。これは制限された関係モデルのようにも見えますね。(1)タプルのうち、先頭からn個の要素のみユニークキーにできる(2)ルックアップは、先頭からk個 (0<=k<=n) の属性値を指定して、残りの属性値からなるタプルの集合を得るprojection。
#あーでもn個のキーを指定したときには具体的な値が返ってくるけどn個より小さい場合は辞書が返ってくるから、そのへんの扱いが微妙だな。
#「集合とハッシュが混在」という上に挙がってる問題点としては、makeする時点でputに渡せる値の個数を指定させちゃうのはだめですか。キーが2個、値が3個、という構造を作ったら、(put d k1 k2 v1 v2 v3) 以外の形で呼び出すとエラー。そもそも「返ってくる値の個数が不定」っていうのはものすごく扱いにくいんで、「getでいくつ値が返ってくるかわからない辞書」ってあんまり便利じゃなさそうな。
#＞koguroさん。http://practical-scheme.net/wiliki/wiliki.cgi?Gauche%3aMemoize のShiro(2013/04/13 14:01:32 UTC):の指摘をもとに、くるくると考えた結果・・・というか迷走というか。 #あと、yamasushiさんはメモ化への応用という観点から出発しているようですが、Schemeでは残念ながら与えられた関数のアリティを確実に知る方法が無いんで、そっちの方は無理筋な気がします。
#>Shiroさん。そうなんです。makeでアリティを指定したほうがいいかなとかとも考えたのでした。というのは、これは関数を定義する表をつくる、という見方もできるからです。
#それが、昨日からくだくだと迷走しているわたしの発言の根本にあります。手続きとデータ構造の対応です。
#>yamasushiさん。いや、http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a多値 を見てて思ったのですが、何かパフォーマンス上の優位点があったり、ある視点に立つと keyとvalueが同一視できたりするのかな、と思ったのですがよくわからなかったので。 #関数と表を対応させられるのは副作用が無いか、極めて単純な場合だけなんで、「set, bag, mapの統一」とは別に考えないとならないんじゃないかな。先に指摘したように、() -> a なthunkにbagを対応させることができるのは、thunkが既知の確率的サンプリングである場合のみだと思います。
#> koguroさん。 ああ、dict-fold,dict-mapではkey,valueの区別はないので、これと同じように、多値のコレクションも定義できそうな気がしたのでした。多値のコレクションという(なぞの)見方は、list処理関数でlistを複数指定したときに対応する・・・・というか。。。すみません、未消化です。
#diff --git a/lib/gauche/dictionary.scm b/lib/gauche/dictionary.scm
index 89910b3..0d39653 100644
--- a/lib/gauche/dictionary.scm
+++ b/lib/gauche/dictionary.scm
@@ -178,10 +178,10 @@
(define-method dict-fold ((dict <dictionary>) proc seed)
;; This depends on the fact that a dictionary is also a collection.
- (fold dict (lambda (kv seed) (proc (car kv) (cdr kv) seed)) seed))
+ (fold (lambda (kv seed) (proc (car kv) (cdr kv) seed)) seed dict))
(define-method dict-fold-right ((dict <ordered-dictionary>) proc seed)
- (fold-right dict (^[kv seed] (proc (car kv) (cdr kv) seed)) seed))
+ (fold-right (^[kv seed] (proc (car kv) (cdr kv) seed)) seed dict))
(define-method dict-map ((dict <dictionary>) proc)
(reverse (dict-fold dict (^[k v s] (cons (proc k v) s)) '())))
#dict-foldで思いだしました。
#ああまだ直してなかった。今push
#しました
#(map cons '(a b c) '(d e f)) -> ((a . d) (b . e) (c . f))
;; 同じ事を多値のコレクションですると：
(define d (duck-dict-make))
(duck-dict-put d 'a 'd)
(duck-dict-put d 'b 'e)
(duck-dict-put d 'c 'f)
(map cons d) ---> ((a . d) (b . e) (c . f))
#(fold cons* '() '(a b c) '(1 2 3)) --> (c 3 b 2 a 1)
;; 同じ事を多値のコレクションですると：
(define d (duck-dict-make))
(duck-dict-put d 'a 1)
(duck-dict-put d 'b 2)
(duck-dict-put d 'c 3)
(fold cons* '() d) ---> (c 3 b 2 a 1)
#(型の問題とかありますが・・・・いま、listを仮定しているので。)
Gauche > Archives > 2013/05/02