跟踪 Ocaml 递归函数

Question

我在跟踪这段代码（正确）时遇到问题：

    let rec prepend (l: int list list) (x: int) : int list list = 
        begin match l with
          | [] -> []
          | hd :: tl -> (x :: hd) :: (prepend tl x)
        end

prepend [[]; [2]; [2;3]] 1 = [[1]; [1;2]; [1;2;3]]

我的跟踪不正确，但我不确定哪里出了问题：

prepend ([]::2::[]::2::3::[]::[]) 1 =
1::[]::prepend (2::[]::2::3::[]::[]) 1 =
1::[]::1::2::prepend([]::2::3::[]::[]) 1 =
1::[]::1::2::1::[]::prepend(2::3::[]::[]) 1 --> 
This is incorrect because then it comes out as [1] ; [1;2;1]
when it should be [1]; [1;2] ; [1;2;3]

Answer 1

:: 运算符不是关联运算符，即 (a :: b) :: c 与 a :: (b :: c) 不同。所以您应该使用括号来跟踪您的子列表。

prepend ([] :: (2 :: []) :: (2 :: 3 :: []) :: []) 1 =>
(1 :: []) :: prepend ((2 :: []) :: (2 :: 3 :: []) :: []) 1 => 
(1 :: []) :: (1 :: 2 :: []) :: prepend ((2 :: 3 :: []) :: []) 1 => ...

也许你可以从那里拿走....

跟踪 Ocaml 递归函数

Tracing Ocaml Recursive Function

recursion

trace

ocaml