let val declarations in SML NJ

Question

I'm having a mental roadblock in understanding how this works and hoping I can get some guidance. The function f below will sort a list of ints (f [1,2,3]). The part I'm stuck on is the val declaration and what is occurring in recursion. I know the val declaration will allow me to compare the second value in the list to the first but I'm getting confused with the list concatenation. It seems like the function would just compare the first two values and then tack on the rest of the list (ie x :: y :: ys). I'm not sure how f ls is actually working. Is it that...

1) The first two values are compared and added to the list

2) then f ls is recursively called?

Seems like that is the case but then I'm confused about the "ys" - seems like the end of the list is tacked on with each call. I know the sort works but not sure how it's actually working.

fun f ([x]) = [x]
|   f(x :: ls) =

let 
    val (y :: ys) = f ls
in
    if y > x then x :: y :: ys
    else
        y :: x :: ys
end

EDIT - Thought about this some more, is it that y::ys within in the in / end body is actually what is being called recursively? If so, SML is smart enough to know that it should use x::ys in y::ys place if it hits else?

Kevin Johnson Kevin Johnson · Accepted Answer · 2015-12-16T18:34:58

First and foremost, the sort doesn't work when the list is very random, e.g. f [2,3,4,1,2,4,6,0,6,7]

Secondly, to answer your question as to how this particular function works, you can visualize it easily with following print additions to your code:

fun f ([x]) = [x]
|   f(x :: ls) = (print( (Int.toString (x)) ^ "\n");

let 
    val (y :: ys) = f ls
    val x_str = Int.toString (x)
    val y_str = Int.toString (y)
    val ys_str = concat (map Int.toString ys);
    val y_gt_x = if y > x then " ---> this one applies " else ""
    val x_gt_y = if x >= y then " ---> this one applies " else ""
in
    (print ("if " ^ y_str ^ " > " ^ x_str ^ 
            "\n      then " ^ x_str ^ " :: " ^ y_str ^ ys_str ^ y_gt_x ^ 
            "\n      else " ^ y_str ^ " :: " ^ x_str ^ ys_str ^  x_gt_y ^ "\n");
    if y > x then x :: y :: ys
    else
        y :: x :: ys)
end)

which for the above random list outputs the following:

- f [2,3,4,1,2,4,6,0,6,7];
2
3
4
1
2
4
6
0
6
if 7 > 6
      then 6 :: 7 ---> this one applies
      else 7 :: 6
if 6 > 0
      then 0 :: 67 ---> this one applies
      else 6 :: 07
if 0 > 6
      then 6 :: 067
      else 0 :: 667 ---> this one applies
if 0 > 4
      then 4 :: 0667
      else 0 :: 4667 ---> this one applies
if 0 > 2
      then 2 :: 04667
      else 0 :: 24667 ---> this one applies
if 0 > 1
      then 1 :: 024667
      else 0 :: 124667 ---> this one applies
if 0 > 4
      then 4 :: 0124667
      else 0 :: 4124667 ---> this one applies
if 0 > 3
      then 3 :: 04124667
      else 0 :: 34124667 ---> this one applies
if 0 > 2
      then 2 :: 034124667
      else 0 :: 234124667 ---> this one applies
val it = [0,2,3,4,1,2,4,6,6,7] : int list
-

As you can see, the function f recursively calls itself in the let binding section. (check the code: let val (y :: ys) = f ls

as you can see, f ls is the recursive call of the function f, so your analysis of y :: ys being the recursive call within the in body is incorrect as that is merely an operation of prepending the element y to the list ys)

The in body does not get evaluated except all the way at the end of the list. So the in body will first evaluate the last two elements of the list, e.g. 7 > 6 and grow the list ys accordingly.

Thirdly, to answer point number one as to why the sort function f doesn't work properly is because it keeps on adding new elements to ys without seeing if the new elements are placed in order in ys with respect to the remainder elements. Yes, the first element of the list ys gets compared with the new element to be prepended and accordingly the biggest of the two will get prepended first to the remainder of ys, but that doesn't guarantee the correct placement with regards to the second and third and so on element of ys.

let val declarations in SML NJ

1 Answers