function - 试图理解 OCaml 中的这段代码

Question

我试图了解这段代码在做什么:

let rec size x =
    match x with
      [] -> 0
    | _::tail -> 1 + (size tail) ;;

我知道这个表达式计算了一个列表的大小，但我不明白它在代码中的什么地方一一缩小了列表。例如，我认为它需要从 [1;2;3] 到 [2;3] 到 [3]，但是它在哪里或如何做到这一点？我不明白。

谢谢。

Answer 1

OCaml 中的列表是使用空列表 ( [] ) 和 cons ( :: ) 构造函数递归构建的。所以[1; 2; 3]是 1::2::3::[] 的语法糖.

大小是通过减少 x 来计算的在每个步骤中使用模式 _::tail ( _ 表示我们忽略列表的头部)并调用相同的函数 size在 tail .当列表为空且模式为 [] 时，该函数最终终止成功。

以下是如何 size [1; 2; 3] 的简短说明计算:

   size 1::2::3::[]
~> 1 + size 2::3::[] // match the case of _::tail
~> 1 + 1 + size 3::[] // match the case of _::tail
~> 1 + 1 + 1 + size [] // match the case of _::tail
~> 1 + 1 + 1 + 0 // match the case of []
~> 3

作为旁注，从图中可以看出，计算 size需要在栈中存储很多信息。 .这意味着如果输入列表很长，您的函数可能会导致堆栈溢出错误，但这是另一回事。