Recursion In simple ML Standard

Question

fun max (xs : int list)=
    if null xs
    then NONE 
    else
    let val tl_ans = max(tl xs)
    in
        if isSome tl_ans andalso valOf tl_ans > hd xs
        then
        tl_ans
        else
        SOME (hd xs)
    end

I can't figure how this program works from my understanding: we enter the else then we call max(tl xs) recursively till it hit none so when we have none we check the if in the in and it will be false then we return SOME(hd xs). the question will be that I can't understand how this program works line by line I feel that I missed something.

molbdnilo · Accepted Answer · 2021-06-18 06:26:34Z

2

I suspect the mistake you're making is trying to reason about several recursions at once.
Focus at just one function call at a time.

Example:

max [] is NONE, as you say.

Next, take max [2] as an example.

This is

let val tl_ans = max []
in
    if isSome tl_ans andalso valOf tl_ans > 2
    then
        tl_ans
    else
        SOME 2
end

which is

if isSome NONE andalso valOf NONE > 2
then
    NONE
else
    SOME 2

which is clearly SOME 2.

Next, try max [3,2]

This is

let val tl_ans = max [2]
in
    if isSome tl_ans andalso valOf tl_ans > 3
    then
        tl_ans
    else
        SOME 3
end

and you know that max [2] is SOME 2, so this is

if isSome (SOME 2) andalso valOf (SOME 2) > 3
then
    SOME 2
else
    SOME 3

which is SOME 3.

And so on...

answered Jun 18, 2021 at 6:26

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion In simple ML Standard

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related