Why does this split function work?

Question

I have function that splits a list into two halfs.

Here is the function :

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

What I don't understand is why this statement works (a::M, b::N). Aren't we calling the recursive function before we execute that statement? So should't that statement never be executed?

Answer 1

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

Yes.

So should't that statement never be executed?

Only if the recursion were infinite, which it is not. As is, (a::M, b::N) will be evaluated once the recursive call finishes.

As an example, consider the call 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])

Nothing infinite going on here.