How does recursion looks like for let-in-end in SML

Question

Could someone teach me how does the recursion looks like for let-val-in-end case? I have a hard time understanding the procession ie the breakdown of the loop [SML]

Example in : How does 'c' behave? I mean the break down

fun less (nil, x) = nil
    | less (a::b, x) = 
    let
        val c = less(b,x)
    in
        if a < x then a::c else c
    end;

or How do x and y behave in each loop? I understand it is deconstructing just like in JS.

fun half nil = (nil,nil) 
| half [a] = ([a],nil)
| half (a::b::xs) = 
    let 
        val (x,y) = half(xs)
    in 
        (a::x, b::y)
    end;
    
half [1,2,3]

Answer 1

Let's take a look at your half function.

fun half nil = (nil, nil) 
  | half [a] = ([a], nil)
  | half (a::b::xs) = 
      let 
        val (x, y) = half(xs)
      in 
        (a::x, b::y)
      end;

How does this reduce out when we evaluate half [1, 2, 3]?

half [1, 2, 3]
(1 :: [3], 2 :: [nil])
([1, 3], [2])

You've recursively called half on xs which in this case is [3]. This returns ([3], [nil]), so you local binding x is [3] and local binding y is [nil]. We cons a and b respectively to those lists and get the final result.

It's important to realize that this is not tail-recursive and with a large enough sample size, a stack overflow will happen.

We can convert it to be tail-recursive, though by using an accumulator. By doing this, all data is passed from one stack frame to the next. There is no need for any previous stack frame to fully evaluate the function. A good compiler will thus optimize it to constant stack space.

The accumulator is a tuple containing two lists.

fun split([], (a, b)) = (a, b)
  | split([x], (a, b)) = split([], (x::a, b))
  | split(x::x'::xs, (a, b)) = split(xs, (x::a, x'::b))

Now, if we call split([1, 4, 7, 2, 89, 12], ([], [])):

split([1, 4, 7, 2, 89, 12], ([], []))
split([7, 2, 89, 12], (1::[], 4::[]))
split([89, 12], (7::1::[], 2::4::[]))
split([89, 12], (7::1::[], 2::4::[]))
split([], (89::7::1::[], 12::2::4::[]))
(89::7::1::[], 12::2::4::[])
([89, 7, 1], [12, 2, 4])

Oops! They're backwards! Let's reverse the accumulators.

fun split([], (a, b)) = (List.rev a, List.rev b)
  | split([x], (a, b)) = split([], (x::a, b))
  | split(x::x'::xs, (a, b)) = split(xs, (x::a, x'::b))

But having to specify that initial accumulator each time we call split is annoying. We can create a local function to hide it.

fun split(lst) =
let
  fun split'([], (a, b)) = (List.rev a, List.rev b)
    | split'([x], (a, b)) = split'([], (x::a, b))
    | split'(x::x'::xs, (a, b)) = split'(xs, (x::a, x'::b))
in
  split'(lst, ([], []))
end;

And then split([1, 3, 7, 2, 6, 8, 0, 3, 7, 5]) yields ([1, 7, 6, 0, 7], [3, 2, 8, 3, 5]).

In summary: the local binding does not intrinsically have anything to do with recursion. Also, tail recursion can be easier to reason about, and prevents stack overflow errors.