为什么这个分离功能有效？

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

在执行该语句之前,我们不是在调用递归函数吗？

是.

那个声明不应该被执行吗？

只有当递归是无限的时,它才是无限的.按原样,(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])

这里没有任何无限的事情发生.