OCaml でリストの map を書くと、素朴には以下のようになるだろう。
let rec map f s =
match s with
| [] -> []
| v :: s' -> f v :: map f s'
標準ライブラリの List.map も、書き方はちょっと違うが、同じようなものである。
<URL:https://github.com/ocaml/ocaml/blob/4.10.0/stdlib/list.ml#L90-L92>
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
ただ、この実装は、tail recursive ではない。
これはマニュアルにも Not tail-recursive. と明記されている。
tail recursive ではないので、リストの長さに比例してスタックを消費する。
なので、とても長いリストに使うと、おそらく不幸なことになる。
では、tail recursive に書こうと思って単純に累積引数を使うと、
リストが逆順になってしまう。
これを実装したものは標準ライブラリの List.rev_map にある。
<URL:https://github.com/ocaml/ocaml/blob/4.10.0/stdlib/list.ml#L100-L105>
let rev_map f l =
let rec rmap_f accu = function
| [] -> accu
| a::l -> rmap_f (f a :: accu) l
in
rmap_f [] l
では、tail recursive で、かつ、逆順にならないように、というなら、
List.rev は tail recursive なので、
List.rev_map と List.rev を組み合わせればいい。
しかし、そうすると、List.rev_map で生成したリストをすぐに捨てることになるので、
メモリの無駄である。(無駄に GC 頻度が上昇する、というほうが正確かも)
では、tail recursive で、逆順にならず、無駄にメモリを確保しない map というのは実装できるか?
少し考えると、リストというのは構造上、先頭から末尾に向かってしか調べられず、
また、リストは末尾から先頭に向かって構築せざるを得ない、
ということから、そういう map は無理っぽいと思える。
しかし、最近、Coq の実装内部に、そういう map の実装が存在することを発見した。
<URL:https://github.com/coq/coq/blob/V8.11.0/clib/cList.ml#L403-L415>
let rec map_loop f p = function
| [] -> ()
| x :: l ->
let c = { head = f x; tail = [] } in
p.tail <- cast c;
map_loop f c l
let map f = function
| [] -> []
| x :: l ->
let c = { head = f x; tail = [] } in
map_loop f c l;
cast c
ここで、head と tail というフィールドをもつレコードと、cast という関数を使っているが、これらは以下のように定義されている。
<URL:https://github.com/coq/coq/blob/V8.11.0/clib/cList.ml#L143-L151>
(** Tail-rec implementation of usual functions. This is a well-known trick used
in, for instance, ExtLib and Batteries. *)
type 'a cell = {
head : 'a;
mutable tail : 'a list;
}
external cast : 'a cell -> 'a list = "%identity"
コメントによれば、これは Coq 独自のアイデアではないようだ。
なにをしているのかというと、コンスセルの tail (cdr) を破壊的に書き換えている。
もちろん OCaml の list 型では書き換えられないのだが、
cell 型では (mutable tail としているので) 書き換えることが可能で、
そうやって書き換えたものを
cast 関数で無理やり list 型に変えてしまっている。
この cast 関数というのは、Obj.magic とだいたい同じもののようある。
Obj.magic は以下のように定義されていて、任意の型から任意の型に変えられるが、
cast は cell 型から list 型へ変換するだけにしか使えないようにされている。
<URL:https://github.com/ocaml/ocaml/blob/4.10.0/stdlib/obj.ml#L22>
external magic : 'a -> 'b = "%identity"
OCaml 内部のメモリ表現を知っていれば、cell 型と
list 型 (の (::) コンストラクタで作られるデータ) が同じ構造になることは
わかるので、こうやって型を変えれば、tail を破壊的に書き換えられる。
tail を破壊的に書き換えられれば、map をうまく実装できる、つまり tail recursive で、逆順にならず、無駄にメモリを確保しない、という実装が可能になる。
つまり「リストは末尾から先頭に向かって構築せざるを得ない」という前提を取り除き、
先頭から末尾に向かって構築することにより、こういう map の実装が可能になる。
まぁ、Lisp や C でリストを扱うなら、
こうやって tail を破壊的に書き換える実装をするのは珍しくないと思うのだが、
OCaml でやっちゃうというのが驚くところである。
なお、ExtLib だとどうなっているか調べると、以下のようになっている。
<URL:https://github.com/ygrek/ocaml-extlib/blob/1.7.6/src/extList.ml#L31-L36>
(* Thanks to Jacques Garrigue for suggesting the following structure *)
type 'a mut_list = {
hd: 'a;
mutable tl: 'a list
}
external inj : 'a mut_list -> 'a list = "%identity"
あー、なるほど、誰が言い出したのかわかったかもしれないですね。
追記:
Garrigue先生に教えてもらったのをもとに調べたところ、
以下のような流れのようだ
ExtLib で以下のように入った
他のプロジェクトでも使われる
それはそれとして、言語自体に仕掛けをいれて、ユーザが破壊的変更を記述せず、
最初に書いたような素朴な関数でも定数サイズのスタックで済むようにしようという話がある
