04/08/19 19:14
>>204
たとえば次のように書くと、
let alist = (word, count+1) :: (List.filter (fun (w, c) -> w <> word) alist)
これは破壊的代入ではないよ。元の alist は破壊されなくて、そこの部分を
書き換えたリストを *新しく* 作る。だから、置き換える前のリストや、消し
たセルを参照しているものがあっても副作用は起きない。
ただしこれ、実際にやると新しくリストをコピーすることになるので、著しく
効率が悪いはず。
Concurrent Clean だと、古い方のものが以後使われることがない(他で参照さ
れていない)時には自動的に破壊的代入になるという話を聞いたことがあるん
だけど、もしそうなら同じアルゴリズムで効率的に動作できるのかも。
そういうわけで、こんな感じかな(OCamlのコードです)。
let rec count x = function
| [] -> x
| y::ys ->
try
let w, c = List.assoc y x in
let x' = (w, c+1) :: (List.filter (fun (w', c') -> w <> w') x) in
count x' ys
with Not_found ->
count ((y, 1) :: x) ys
try - with で囲んでるから末尾再帰じゃないので、さらに効率的ではないけ
どね。