Erlang Super Lite(仮) 準備会へ行ってきた
http://atnd.org/events/1845へ参加.
id:voluntasの話が凄過ぎて圧倒されっぱなし.
実際にErlangを業務でバリバリ使っている方ならではの,Erlangの特徴や使っているツール・効果的な学習法・裏話を聞くことが出来た.
ホットスワップが,業務的に許されないケースの話や,デバッグの難しさ等,短所の話も聞けたのは良かった.
キチンとした纏めは他の方が書いてくれると思うので,初めて書いたマインドマップを.
Erlang Programming: A Concurrent Approach to Software Development
- 作者: Francesco Cesarini,Simon Thompson
- 出版社/メーカー: O'Reilly Media
- 発売日: 2009/06/29
- メディア: ペーパーバック
- 購入: 1人 クリック: 44回
- この商品を含むブログ (21件) を見る
SICP 2.32 (冪集合)
「集合のすべての部分集合の集合をリストのリストとして表現せよ」という問題.
冪集合という言葉は出てないけど,冪集合そのもの.
wikipedia:冪集合
P(X):=集合Xの部分集合の集合(冪集合)
と定義する.このとき
P(X)={Xから先頭の要素xを除いた集合の冪集合と、その各要素にxを加えた集合の和集合}
と再帰的に書けるので,これをそのまま適用してあげれば解答になる.
つまり、X={a,b,c}について
P(X)=P{b,c}∪(P{b,c}の全ての要素にaを加えたもの)
のような感じ.
私は最初に問題を見た時は,以下のように考えた.
集合の要素として含む/含まないをビットが立っているかで表すと、
P{b,c}は、以下のように書ける.
b | c | |
---|---|---|
0 | 0 | |
0 | 1 | |
1 | 0 | |
1 | 1 |
P{a,b,c}は,以下のように書ける.
a | b | c |
---|---|---|
0 | 0 | 0 |
0 | 0 | 1 |
0 | 1 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
1 | 1 | 1 |
aが0と1の時のそれぞれについて,bとcについてはP{b,c}と同じ形.
このことから,P{b,c}に,aを加えてあげたものを足せばよいということが分かる.
なので,この場合,
rest=(subsets (cdr '(a b c))=(subset '(b c))と考えると
(subsets '(a b c))=(append rest (map (aをリストに加える手続き) rest)
とすれば良さそうということが分かり,
解答としては,
(lambda (x) (cons (car s) x))
を入れれば良いことが分かる.
また,上記のように,ビットのON/OFFで集合に含まれるかどうかを表すと,
二進数と各部分集合が1:1に対応するので,n個の要素を持つ集合に対して,
まで2進数をカウントアップしていけば個の部分集合からなる冪集合を作ることができる.
この方法だと再帰的ではない書き方も可能.