functional-programmingsml

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

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]
``````

Solution

• 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.