functional-programmingml

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.


Solution

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