recursion - 为什么这个拆分功能有效？

Question

我有一个将列表分成两半的函数。

函数如下:

  let rec split = function
  | []       -> ([],[])
  | [a]      -> ([a],[])
  | a::b::cs -> let (M,N) = split cs
                (a::M, b::N)

我不明白为什么这个语句有效 (a::M, b::N)。我们不是在执行该语句之前调用递归函数吗？那么不应该永远执行该语句吗？

Answer 1

Aren't we calling the recursive function before we execute that statement?

是的。

So should't that statement never be executed?

仅当递归是无限的时，它不是。按照原样，递归调用完成后将对 (a::M, b::N) 进行求值。

例如，考虑调用 split [1;2;3]:

  split [1;2;3]
= let (M,N) = split [3]
  (1::M, 2::N)
= let (M,N) = ([3], [])
  (1::M, 2::N)
= (1::[3], 2::[])
= ([1;3], [2])

这里没有无限的事情发生。