飯吹いた
オレオレマージソートの一部
let rec merge_two ls1 ls2 ret = match ls1, ls2 with | x1 :: xs1, x2 :: xs2 -> if (comp x1 x2) then merge_two xs1 ls2 (x1 :: ret) else merge_two ls1 xs2 (x2 :: ret) | ls1, [] -> rev_append ls1 ret | [], ls2 -> rev_append ls2 ret in let rec merge_two_rev ls1 ls2 ret = match ls1, ls2 with | x1 :: xs1, x2 :: xs2 -> if (comp x2 x1) then merge_two_rev xs1 ls2 (x1 :: ret) else merge_two_rev ls1 xs2 (x2 :: ret) | ls1, [] -> rev_append ls1 ret | [], ls2 -> rev_append ls2 ret in
標準ライブラリの(マージ)ソートの一部
let rec rev_merge l1 l2 accu = match l1, l2 with | [], l2 -> rev_append l2 accu | l1, [] -> rev_append l1 accu | h1::t1, h2::t2 -> if cmp h1 h2 <= 0 then rev_merge t1 l2 (h1::accu) else rev_merge l1 t2 (h2::accu) in let rec rev_merge_rev l1 l2 accu = match l1, l2 with | [], l2 -> rev_append l2 accu | l1, [] -> rev_append l1 accu | h1::t1, h2::t2 -> if cmp h1 h2 > 0 then rev_merge_rev t1 l2 (h1::accu) else rev_merge_rev l1 t2 (h2::accu) in
なんかまる写ししたみたいだ。
OCamlの罠
ソフトウェアの授業の課題のソーティングプログラムをOCamlで書き始めてから、度重なるStack overflowに悩むこと1週間。ファイル読み込み時のstack overflowは普通に末尾再帰に書き直してうまくいったけど、2つのリストをマージする関数に2,000,000要素くらいのリストを渡すとどうやってもstack overflowになってしまう。末尾再帰の書き方を変えてもダメ。なんなんだー!と思ってocamloptでネイティブコンパイルしてobjdumpして自分自身をcallしていないか探すが見つからず。ふとcamlList__appendに目が停まる。というのも、"OCaml 末尾再帰"でググったときに"...するとなんとかして末尾再帰なappendが書ける..."みたいな文章を目にしていたから。これはもしや、と思ってOCamlのマニュアル読んだら案の定appendは末尾再帰じゃなかった\(^O^)/結果返すときにappend使ってるから確実にstack overflowするようになってます本当に(ry
List.rev_append使ったら普通にStack overflowの問題解決。大きなデータのソーティングみたいなある種の極限状態では、組み込み関数を疑うことも重要ってことか。要はRead the F**king Manualということですね。