第3章 練習問題 6-10
6 状態不変表明
P(R,Ys) = (Reverse(Xs) = R + Reverse(Ys))
ただし、ここで+はAppendを表す。
証明は必要かどうかわからないから、省略で。
8 反復的append
fun {Append Xs Ys}
fun {Reverse R Xs}
case Xs
of nil then R
[] X|Xr then {Reverse X|R Xr}
end
end
fun {ReverseAppend R Xs}
case Xs
of nil then R
[] X|Xr then {ReverseAppend X|R Xr}
end
end
in
{Reverse nil {ReverseAppend {Reverse nil Xs} Ys}}
end
9 反復計算とデータフロー変数
実際にデータフロー変数を使わずに、appendを定義することができた。
10 あるものがリストであるかどうかをチェックすること
変更すると{Leaf [1 2 3]}のようにリストを引数として与えるとブロックする。
2.8.2節において
内包チェック
== (および、その逆の反駁チェック \= )は二引数の関数で、 と の等・不等が分かるまでブロックする。内包チェックも反駁チェックも束縛は行なわない。
とある。
そのため、X \= _|_はXがリストの場合、_|_の内容が分かるまでブロックする。次のように書きなおすとこのことがはっきりする。
fun {Leaf2 L} X Xr in
% XとXrが分かるまでブロックする
L == X|Xr
end
11 差分リストの限界
ここで問題といわれているのは、
local X Y Z in
local
D1 = (1|2|3|X)#X
D2 = (4|5|6|Y)#Y
D3 = (7|8|9|Z)#Z
in
{Show {AppendD D1 D2}}
% (1)
{Show {AppendD D1 D3}}
end
endという状況。
ここで、一度目のAppendD終了後(1の位置)でD1は(1|2|3|4|5|6|Y)#(4|5|6|Y)に束縛されている。
これを二度目のAppendDに渡すと、4|5|6|Yを7|8|9|Zで束縛しようとする。そのためエラーが発生する。
12 リストの平坦化の計算量
分からない。nとkが両方パラメータで、どう漸化式を解いたらいいか分からない。
直感によるとFlattenはO(n*n)でFlattenDはO(n)。
13 行列操作
転置と積だけ。
fun {Trans M}
fun {Split Xs}
case Xs
of (Y|Yr)|Xr then
Hs#Ts = {Split Xr}
in
(Y|Hs)#(Yr|Ts)
else nil#nil end
end
fun {Join Ys Xs}
case Ys#Xs
of (Y|Yr)#(X|Xr) then (Y|X)|{Join Yr Xr}
else nil end
end
in
case M
of nil then nil
[] [[X]] then [[X]]
[] (X|Xr)|Ys then
Y#Yr = {Split Ys}
in
(X|Y)|{Join Xr {Trans Yr}}
end
end
fun {Mul M1 M2}
fun {Product Xs Ys}
case Xs#Ys
of (X|Xr)#(Y|Yr) then (X*Y)+{Product Xr Yr}
else 0 end
end
M3 = {Trans M2}
in
{Map M1 fun {$ X}
{Map M3 fun {$ Y} {Product X Y} end}
end}
end
14 FIFOキュー
(a)
Xが未束縛のままになる。
(b)
キューに何かが挿入されている場合、SとEの等価性を判定するにはSとEが共に束縛されていなければならない。
しかし、Eは常に自由なので、ブロックしてしまう。
15 クイックソート
fun {QSort Xs}
proc {QSortD Xs ?Y1 Y}
case Xs
of nil then Y1 = Y
[] X|Xr then
L1 = {Filter Xr fun {$ V} V < X end}
L2 = {Filter Xr fun {$ V} V >= X end}
Z
in
{QSortD L1 Y1 X|Z}
{QSortD L2 Z Y}
end
end
Y1
in
{QSortD Xs Y1 nil}
Y1
end
16 末尾再帰の畳み込み
fun {Zip Xs Ys}
fun {Iter Xs Zs}
case Xs
of nil then
Zs = Ys
nil
[] X|Xr then Z in
(X#Z)|{Iter Xr Z|Zs}
end
end
in
{Iter Xs nil}
end(X#Z)|{Iter ...}は核言語に変換するときに、末尾再帰になるはず。
ヒントを正しく活用していない気がするが、単一化の特徴を使っているし、問題ないはず。
17 カリー化
gumpの使い方を調べるのが大変なので、後回し。
