CODEWITHSUNDEEP
functional-programmingml
Antutu Cat
Antutu Cat

Reputation: 105

Recursion In simple ML Standard

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.

Upvotes: 0

Views: 60

Answers (1)

molbdnilo
molbdnilo

Reputation: 66371

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

Upvotes: 2

Related Questions