Objective Caml 入門 手習い（5章）その4

いよいよ5章の演習問題最大の山場（と勝手に思っている）quick sortの書き換え問題です。

Exercise 6

問題

Exercise6 quick 関数を @ を使わないように書き換える．quicker は未ソートのリスト l と，sorted というソート済でその要素の最小値 が l の要素の最大値より大きいようなリストを受け取る． 定義を完成させよ．
let rec quicker l sorted = ...

自分の答え

(* Exercise 6 *)
(* original *)
let rec quick = function
  | [] -> []
  | [x] -> [x]
  | x :: xs ->  (* x is the pivot *)
      let rec partition left right = function
        | [] -> (quick left) @ (x :: quick right)
        | y :: ys -> if x < y then partition left (y :: right) ys
          else partition (y :: left) right ys
      in partition [] [] xs
;;

let partition f l =
  let rec partition_ l fmr ltr =
    match l with
    | [] -> fmr, ltr
    | x::xs ->
        if f x then partition_ xs (x::fmr) ltr
        else partition_ xs fmr (x::ltr)
  in
  partition_ l [] []
;;
        
let rec quicker l sorted =
  match l with
  | [] -> sorted
  | x::xs -> 
      let smallers, biggers = partition (fun y -> y < x) xs in
      quicker smallers (x :: quicker biggers sorted)
;;

let rec quicker_tail l k =
  match l with
  | [] -> k []
  | x::xs ->
      let smallers, biggers = partition (fun y -> y < x) xs in
      let at x y = List.rev_append (List.rev x) y in
      quicker_tail smallers (fun sorted_s -> 
        quicker_tail biggers (fun sorted_b -> k (at sorted_s (at [x] sorted_b))))
;;

let print_list_d l = 
  begin
    Printf.printf "[";
    List.map (Printf.printf "%d; ") l;
    Printf.printf "]\n";
  end;
;;

print_list_d (quicker_tail [2;4;5;3;0;3;10;9;4;7] (fun x -> x));;

感想

この課題としてはリスト結合演算子を使わないというのが条件だったので真ん中のquickerが答えになるんだろうけど、末尾っぽくなってないので気持ち悪いと言ったら id:camlsportter にいろいろご指導いただいて継承渡しスタイルで書けました。
継承渡しスタイル(CPS)については詳しいサイトがあるのでここでは割愛して自分が詰まったのはどうやって継続していくのかという部分。ここは @_2F_1 に教えてもらって納得。
普通の末尾再帰の場合

let rec fact res = function
  | 1 -> res
  | n -> fact (n*res) (n-1)
;;

fact 1 5;;

という感じでresの部分はそのままの形で渡されて初期値は実行時に渡されます。同じようにCPSの場合は次のようになります。

let rec fact cont = function
  | 1 -> cont 1
  | n -> fact (fun x -> cont (n*x)) (n-1)
;;

fact (fun x -> x) 5;;

ここでcontの部分は継続渡しスタイルになっているわけですが、常にcontの部分が新しい関数になっているのが分かります。値を渡した末尾再帰では値が育っていったように、継続渡しでは関数が育っていくようです。
くわしくはこちら参照。

• M.Hiroi's Home Page / お気楽 OCaml プログラミング入門