ocamlのトレースでパラメータがと表示されるケース
昨日のような簡単な再帰関数だとトレース結果もわかりやすいので、もうちょっと複雑なクイックソートのトレースを見てみました。
let rec quick_sort lst = let take n lst p = List.filter (fun item -> p item n) lst in let take_less n lst = take n lst (<) in let take_greater n lst = take n lst (>) in let take_equal n lst = take n lst (=) in match lst with [] -> [] | first :: rest -> quick_sort (take_less first rest) @ take_equal first lst @ quick_sort (take_greater first rest)
# #trace quick_sort;; quick_sort is now traced. # quick_sort [5; 4; 9; 8; 2; 3];; quick_sort <-- [<poly>; <poly>; <poly>; <poly>; <poly>; <poly>] quick_sort <-- [<poly>; <poly>] quick_sort <-- [] quick_sort --> [] quick_sort <-- [<poly>] quick_sort <-- [] quick_sort --> [] quick_sort <-- [] quick_sort --> [] quick_sort --> [<poly>] quick_sort --> [<poly>; <poly>] quick_sort <-- [<poly>; <poly>; <poly>] quick_sort <-- [] quick_sort --> [] quick_sort <-- [<poly>; <poly>] quick_sort <-- [<poly>] quick_sort <-- [] quick_sort --> [] quick_sort <-- [] quick_sort --> [] quick_sort --> [<poly>] quick_sort <-- [] quick_sort --> [] quick_sort --> [<poly>; <poly>] quick_sort --> [<poly>; <poly>; <poly>] quick_sort --> [<poly>; <poly>; <poly>; <poly>; <poly>; <poly>] - : int list = [2; 3; 4; 5; 8; 9]
するとこんなふうにパラメータが
多相関数だとこうなるみたいです。polyはpolymorphicの意味ですね。
局所定義しているtakeのパラメータnをintにしてみるとトレースがちゃんと表示されました。
let rec quick_sort lst = let take (n: int) lst p = List.filter (fun item -> p item n) lst in let take_less n lst = take n lst (<) in let take_greater n lst = take n lst (>) in let take_equal n lst = take n lst (=) in match lst with [] -> [] | first :: rest -> quick_sort (take_less first rest) @ take_equal first lst @ quick_sort (take_greater first rest)
# #trace quick_sort;; quick_sort is now traced. # quick_sort [5; 4; 9; 8; 2; 3];; quick_sort <-- [5; 4; 9; 8; 2; 3] quick_sort <-- [9; 8] quick_sort <-- [] quick_sort --> [] quick_sort <-- [8] quick_sort <-- [] quick_sort --> [] quick_sort <-- [] quick_sort --> [] quick_sort --> [8] quick_sort --> [8; 9] quick_sort <-- [4; 2; 3] quick_sort <-- [] quick_sort --> [] quick_sort <-- [2; 3] quick_sort <-- [3] quick_sort <-- [] quick_sort --> [] quick_sort <-- [] quick_sort --> [] quick_sort --> [3] quick_sort <-- [] quick_sort --> [] quick_sort --> [2; 3] quick_sort --> [2; 3; 4] quick_sort --> [2; 3; 4; 5; 8; 9] - : int list = [2; 3; 4; 5; 8; 9]
プログラミングの基礎 (Computer Science Library)
- 作者: 浅井健一
- 出版社/メーカー: サイエンス社
- 発売日: 2007/03
- メディア: 単行本
- 購入: 17人 クリック: 409回
- この商品を含むブログ (126件) を見る