How do I find largest number in List in SML

Question

We want to find the largest value in a given nonempty list of integers. Then we have to compare elements in the list. Since data values are given as a sequence, we can do comparisons from the beginning or from the end of the list. Define in both ways. a) comparison from the beginning b) comparison from the end (How can we do this when data values are in a list?)

What I have done is find the largest number by comparison from the beginning.

How can I do it from the end? What logic should I apply?

Here is my code for comparing from the beginning.

- fun largest[x] = x
= | largest(x::y::xs) =
= if x>y then largest(x::xs) else largest(y::xs)
= | largest[] = 0;
val largest = fn : int list -> int


output

- largest [1,4,2,3,6,5,4,6,7];
val it = 7 : int

Solution 1

In your function, first two elements of the list are compared and the bigger value is compared to the remaining elements. I think comparison from the end means that you try to find the largest number of the tail of the list first and compare it with the head element later.

fun largest [] = raise Empty 
 | largest [x] = x
 | largest (x::xs) =
      let 
        val y = largest xs
      in
        if x > y then x else y
      end

Although it is not required, you should handle the case of empty list for completeness. And you can shorten the function if using max function.

fun largest [] = raise Empty 
 | largest [x] = x
 | largest (x::xs) = max(x, largest xs)

To be honest, I would prefer your version which is tail-recursive (it doesn't blow the stack on big lists). My function could be rewritten to be tail-recursive as other answers demonstrated, but certainly it is more sophisticated than your function.

Solution 2

As @pad demonstrates with his code, the logic that should be applied is making a recursive call that solves the sub-problem recursively before solving the problem of the current scope of the function.

In the case of largest, there is not really any point in solving it backwards, since it simply uses more stack space, which becomes apparent when executing the code "by hand". The design pattern is however useful in other situations. Imagine a function called zip:

(* zip ([1,2,3,4], [a,b,c]) = [(1,a),(2,b),(3,c)] *)
fun zip (x::xs, y::ys) = (x,y) :: zip (xs, ys)
  | zip _ = []

This function turns a tuple of two lists into a list of many tuples, discarding left-over values. It may be useful in circumstances, and defining it is not that bad either. Making its counterpart, unzip, is however slightly trickier:

(* unzip ([(1,a),(2,b),(3,c)] = ([1,2,3],[a,b,c]) *)
fun unzip [] = ([], [])
  | unzip ((x,y)::xys) =
    let
      val (xs, ys) = unzip xys
    in
      (x::xs, y::ys)
    end

Running the regular "from the beginning"-largest by hand might look like this:

   largest [1,4,2,3,6,5,4,6,7]
~> largest [4,2,3,6,5,4,6,7]
~> largest [4,3,6,5,4,6,7]
~> largest [4,6,5,4,6,7]
~> largest [6,5,4,6,7]
~> largest [6,4,6,7]
~> largest [6,6,7]
~> largest [6,7]
~> largest [7]
~> 7

Running the "from the end"-largest by hand, imagining that every indentation level requires saving the current context of a function call in stack memory, calling a new function and returning the result after the ~> arrow, might look like this:

largest [1,4,2,3,6,5,4,6,7] ~> 7
 \_
   largest [4,2,3,6,5,4,6,7] ~> 7
    \_
      largest [2,3,6,5,4,6,7] ~> 7
       \_
         largest [3,6,5,4,6,7] ~> 7
          \_
            largest [6,5,4,6,7] ~> 7
             \_
               largest [5,4,6,7] ~> 7
                \_
                  largest [4,6,7] ~> 7
                   \_ 
                     largest [6,7] ~> 7
                      \_
                        largest [7] ~> 7

So why are these non-tail-recursive functions that make early recursive calls useful if they simply use more memory? Well, if we go back to unzip and we want to solve it without this annoying "thinking in reverse", we have a problem constructing the new result, which is a tuple, because we don't have anywhere to put the x and y:

(* Attempt 1 to solve unzip without abusing the call stack *)
fun unzip [] = ([], [])
  | unzip ((x,y)::xys) = ...something with x, y and unzip xys...

One idea for making such a place would to create an auxiliary function (helper function) that has a few extra function parameters for building xs and ys. When the end of the xys list is reached, those values are returned:

(* Attempt 2 to solve unzip without abusing the call stack *)
local
  fun unzipAux ([], xs, ys) = (xs, ys)
    | unzipAux ((x,y)::xys, xs, ys) = unzipAux (xys, x::xs, y::ys)
in
  fun unzip xys = unzipAux (xys, [], [])
end

But you might have realized that those (xs, ys) end up reversed in the result. A quick way to fix this is by using rev on them, once only, which is best achieved at the base case:

(* Attempt 3 to solve unzip without abusing the call stack *)
local
  fun unzipAux ([], xs, ys) = (rev xs, rev ys)
    | unzipAux ((x,y)::xys, xs, ys) = unzipAux (xys, x::xs, y::ys)
in
  fun unzip xys = unzipAux (xys, [], [])
end

Which brings forth an interesting question: How is rev implemented?

Solution 3

I suggest using a tail recursive helper, which passes the current maximum as an accumulator.

local
    fun helper max [] = max
      | helper max (n::ns) = helper (if n > max then n else max) ns
in
    fun largest ns = helper 0 ns
end;

Solution 4

(*Find the max between two comparable items*)
fun max(a,b) = if a>b then a else b;
(*Find the max item in list which calls the maxL function recursively*)
fun maxL(L) = if L=[] then 0 else max(hd(L), maxL(tl(L)));

View more solutions