OCamlを学習中で引数のリストが明示的ではない時にtraceしても具体的な値が確認できず再帰のイメージがわかなかったので型を明示的にして確認したメモ。

merge.ml

(* merge : int list -> int list -> int list *)
let rec merge list1 list2 = match (list1, list2) with
  | ([], []) -> []
  | ([], first2 :: rest2) -> list2
  | (first1 :: rest1, []) -> list1
  | (first1 :: rest1, first2 :: rest2) ->
    if first1 < first2
    then first1 :: merge rest1 list2
    else first2 :: merge list1 rest2

mergeを定義した段階でリストの中の型はどの型でもOKの「'a」になっている。
traceしても<poly>になって何を渡しているかわからない。

# #use "merge.ml";;
val merge : 'a list -> 'a list -> 'a list = <fun>
# #trace merge;;
merge is now traced.
# merge [1; 3][2; 4];;
merge <-- [<poly>; <poly>]
merge --> <fun>
merge* <-- [<poly>; <poly>]
merge <-- [<poly>]
merge --> <fun>
merge* <-- [<poly>; <poly>]
merge <-- [<poly>]
merge --> <fun>
merge* <-- [<poly>]
merge <-- []
merge --> <fun>
merge* <-- [<poly>]
merge* --> [<poly>]
merge* --> [<poly>; <poly>]
merge* --> [<poly>; <poly>; <poly>]
merge* --> [<poly>; <poly>; <poly>; <poly>]
- : int list = [1; 2; 3; 4]

リストには文字列も入れる。

# merge ["a"; "d"]["c"; "b"];;
merge <-- [<poly>; <poly>]
merge --> <fun>
merge* <-- [<poly>; <poly>]
merge <-- [<poly>]
merge --> <fun>
merge* <-- [<poly>; <poly>]
merge <-- [<poly>]
merge --> <fun>
merge* <-- [<poly>]
merge <-- [<poly>]
merge --> <fun>
merge* <-- []
merge* --> [<poly>]
merge* --> [<poly>; <poly>]
merge* --> [<poly>; <poly>; <poly>]
merge* --> [<poly>; <poly>; <poly>; <poly>]
- : string list = ["a"; "c"; "b"; "d"]

引数のリストの中を明示的にintにする。

merge.ml

(* merge : int list -> int list -> int list *)
let rec merge (list1:int list) (list2: int list) = match (list1, list2) with
  | ([], []) -> []
  | ([], first2 :: rest2) -> list2
  | (first1 :: rest1, []) -> list1
  | (first1 :: rest1, first2 :: rest2) ->
    if first1 < first2
    then first1 :: merge rest1 list2
    else first2 :: merge list1 rest2

具体的な値がtraceされるのでイメージしやすい。

# #use "merge.ml";;
val merge : int list -> int list -> int list = <fun>
# #trace merge;;
merge is now traced.
# merge [1; 3][2; 4];;
merge <-- [1; 3]
merge --> <fun>
merge* <-- [2; 4]
merge <-- [3]
merge --> <fun>
merge* <-- [2; 4]
merge <-- [3]
merge --> <fun>
merge* <-- [4]
merge <-- []
merge --> <fun>
merge* <-- [4]
merge* --> [4]
merge* --> [3; 4]
merge* --> [2; 3; 4]
merge* --> [1; 2; 3; 4]
- : int list = [1; 2; 3; 4]