试图理解OCaml中的这段代码

Question

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

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

我知道这个表达式计算列表的大小,但我不明白它在代码中的位置逐一减少了列表.例如,我认为它需要从[1; 2; 3]到[2; 3]到[3],但是在哪里或如何做到这一点？我不明白.

谢谢.

Answer 1

OCaml中的列表是使用空list([])和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.这意味着如果输入列表很长,您的函数可能会导致堆栈溢出错误,但这是另一个故事.