Getting max value from a list in SML

Question

I'm currently studying SML and I'm having a hard time understanding the code below

fun good_max (xs : int list) =
  if null xs
  then 0
  else if null (tl xs)
  then hd xs
  else
    (* for style, could also use a let-binding for (hd xs) *)
    let val tl_ans = good_max(tl xs)
    in
      if hd xs > tl_ans
      then hd xs
      else tl_ans
    end

hd xs is of type int and tl_ans, I think is of type list. Why does this code work? How does the system evaluate the recursion? It would be great if you could use xs = [3, 4, 5] to show me how this works.

` let val y = old_max(tl[3,4,5]) in max(hd[3,4,5], y) end let val y = (let val y' = old_max(tl(tl[3,4,5))) in max(hd(tl[3,4,5],y')) end) in max(hd[3,4,5],y) let val y = (let val y' = old_max([5]) in max(4,y') end) in max(3,y) end let val y = 5 in max (3,y) 5` — fardown
ok. I mess up in trying to put code in the comment box. Thanks Andreas! I was able to figure out how yours work and applied it to my code. Using a helper function made the code more elegant :) My mistake in my assumptions happened because I didn't substitute all of the branches before I evaluated the function. Recursion is really a challenging topic. — fardown
FWIW, the max function already exists in the standard library as Int.max. Also, the right-hand side of the third case could obviously be simplified to just max(x, goodMax xs) -- I didn't do that to demonstrate how reduction inside a let works. Finally, I would suggest rather throwing an exception in the empty case, since 0 is not quite right as a result. Altogether, you can then express the function with a fold as simply fun goodMax [] = raise Empty | goodMax(x::xs) = List.foldl Int.max x xs. — Andreas Rossberg

Andreas Rossberg Andreas Rossberg · Accepted Answer · 2013-12-29T09:10:26

Let me first rewrite this code to an equivalent but more readable version:

fun max(x,y) = if x > y then x else y

fun goodMax(nil) = 0
  | goodMax(x::nil) = x
  | goodMax(x::xs) = let val y = goodMax(xs) in max(x,y) end

Now we can consider how evaluation of goodMax([3,4,5]) proceeds: conceptually, it will be reduced to an answer by repeatedly substituting the respective branch of the function definition(s):

  goodMax([3,4,5])
= goodMax(3::[4,5])
= let val y = goodMax([4,5]) in max(3, y) end
= let val y = goodMax(4::[5]) in max(3, y) end
= let val y = (let val y' = goodMax([5]) in max(4, y') end) in max(3, y) end
= let val y = (let val y' = goodMax(5::nil) in max(4, y') end) in max(3, y) end
= let val y = (let val y' = 5 in max(4, y') end) in max(3, y) end
= let val y = max(4, 5) in max(3, y) end
= let val y = (if 4 > 5 then 4 else 5) in max(3, y) end
= let val y = 5 in max(3, y) end
= max(3, 5)
= if 3 > 5 then 3 else 5
= 5

I have renamed the y in the inner invocation to y' for clarity.

Getting max value from a list in SML

1 Answers