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]