CODEWITHSUNDEEP
recursionfunctional-programmingsml
blue-sky
blue-sky

Reputation: 53786

How does let work in this function?

This function finds the max number of a list and im having difficulty understanding it : 

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

How is tl_ans being computed in line if isSome tl_ans andalso valOf tl_ans > hd xs since it has not been set yet ?

Upvotes: 1

Views: 81

Answers (3)

sshine
sshine

Reputation: 16105

This is not the most idiomatic way to write such a function in Standard ML. Writing it in another way, I propose, will give a better understanding of how it works. The functions valOf, hd and tl are so-called partial functions and the only excuse for using them is when assuring that their input is not NONE or [] respectively (in which case the program will invoke an exception).

Using valOf, hd or tail will thus require you to check if a list is empty (e.g. null xs) or an option exists (e.g. isSome ans), and so the convenience of using it is limited. Instead, using pattern matching (or more robust versions of those functions) is desired.

Below I have written the same function in two other ways, one of which resembles the one you supply.

(* For a list with at least one element in it, check to see if there is a
 * greatest element in the tail (xs). If there isn't, then x is the greatest
 * element. Otherwise, whichever is the greatest of x and y is the greatest.
 *
 * This solution is comparable to the one you have above: Find a solution
 * for the "smaller" problem (i.e. the reduced list in which x isn't in),
 * and then combine the solution. This means making a recursive call to a
 * function that doesn't exist at the time of writing it. *)
fun max [] = NONE
  | max (x::xs) =
    (case max xs of
         NONE   => SOME x
       | SOME y => SOME (Int.max (x, y)))

(* If we were to use a let-expression instead of a case-of, but still restrict
 * ourselves from using partial functions, we might make a helper function: *)
fun maxOpt (x, NONE) = SOME x
  | maxOpt (x, SOME y) = SOME (Int.max (x, y))

(* Now the essence of the let-expression is boiled down: It finds the largest
 * value in the tail, xs, and if it exists, finds the largest of that and x,
 * and pass it as a result packed in SOME. *)
fun max [] = NONE
  | max (x::xs) =
    let val y_opt = max xs
    in maxOpt (x, y_opt) end

(* In fact, one can store the largest value so far in the front of the list.
 * This is only because the return type is int option, and the input type is
 * int list. If the return type were dramatically different, it might not be
 * so easy. *)
fun max [] = NONE
  | max (x::y::xs) = max (Int.max (x,y)::xs)
  | max [x] = SOME x

Upvotes: 2

molbdnilo
molbdnilo

Reputation: 66371

The lines

let val tl_ans =  max1(tl xs)
in 
    if isSome tl_ans andalso valOf tl_ans > hd xs

mean let the value of tl_ans be max1 (tl xs) in the following code.
(You usually say that the value of max1 (tl xs) is bound to the name (or variable) "tl_ans".)

It means exactly the same as

if isSome (max1 (tl xs)) andalso valOf (max1 (tl xs)) > hd xs

except that the value max1 (tl xs) is only computed once.

Upvotes: 2

Marimuthu Madasamy
Marimuthu Madasamy

Reputation: 13531

The function has two cases:

1) Base case - List is empty There is no maximum, return NONE

2) List is not empty - Since the list is not empty, the list will have a head (the first element) and a tail (all elements except the first). Note that the tail will be empty for a list with one element.

The idea here is that for non-empty lists, calculate the maximum for the tail of the list recursively, tl_ans ("tail answer" or maximum among the tail) in your function. Since we know the maximum among all the elements except the first element (the head), now the maximum of the whole list is just the maximum among tl_ans and head of the list.

On each recursive call, the input size is reduced by 1 because we are just passing the tail of the list (that is, without first element). This would finally call the base case when it has got a list with only one element for which the tail is empty. From there, on it's way back from each recursive call, the head for that recursive call would be compared with what returned from the recursion.

Here is an illustration:

max [5,2,6,4]

tl_ans = max [2,6,4], hd = 5
         |
         |=>tl_ans = max [6,4], hd = 2
                   |
                   |=>tl_ans = max [4], hd = 6
                               |
                               |=>tl_ans = max [], hd = 4
                                           |
                                           |<= None (Base case)

                                <= Some 4, comparing tl_ans (None) and hd (4)
                    <== Some 6, comparing tl_ans (Some 4) and hd (6)
        <= Some 6, comparing tl_ans (Some 6) and hd (2)
<= Some 6, comparing tl_ans (some 6) and hd (5)

Upvotes: 3

Related Questions