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
```

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.

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?*

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;
```

```
(*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)));
```

I know it is too late to answer your question, but hopefully this will help:

```
fun insert (x, []) = [x]
| insert (x, y::ys) = if x<=y then x::y::ys else y::insert(x,ys);
fun insertion_sort [] = []
| insertion_sort (x::xs) = insert(x, insertion_sort xs);
fun get_last_element [] = 0
| get_last_element [x] = x
| get_last_element (x::xs) = if(xs=nil)
then x
else
get_last_element(xs);
fun get_min L = if(insertion_sort(L)=[])
then 0
else
hd(insertion_sort(L));
fun get_max L = get_last_element(insertion_sort(L));
```

You also can tweak the code e.g. passing anonymous function in insert function ...

Similar Questions

Is there a fast algorithm for finding the Largest Common Substring in two strings or is it an NPComplete problem? In PHP, I can find a needle in a haystack: <?php if (strstr(there is a needle in a

I have a list with several very big values set on purpose to differentiate those indexes, it looks like this: a = [1.3, 2.1, 9999., 5., 3.7 ,6.6, 9999., 7.4, 9999., 3.5, 7, 1.2, 9999.] I need to find

After a command is executed in SML, it is returned which has the data and the type returned from the command. For example: false; val it = false : bool Let's say I have a binding in a program like

Here is a simple double array: array=[3 1 1] Largest element index is 1 or: array=[3 9 1] Largest element index is 2 How can I get the largest element index?

I don't have any idea how to display the largest and smallest number after the user enter -1. Note: I also have to display the sum of all of this number and the average of this sum. Here's my code so

How can I find the largest quadrangle in this case? In the attached image you can see what I have (in the left) and what I wantto get (in the rigth). This code won't work because the largest rectangl

I have an array and am trying to extract the vlaues. I have tried to find the length of the array, but as the array isnt always full the .length doesnt work for me. How do i work out how many values a

How do I use SML/NJ to run a script which reads from STDIN and writes to STDOUT say? Is there a way to get rid of the output from the interpreter itself?

In Python how do I find all the missing days in a sorted list of dates?

I need to take a number from a list and convert it to a number so that i can pass it as a parameter. im trying to make a 1-bit adder in scheme. i've written the code for the or gate and the xor gate a

using Joda Time how do I find the number of milliseconds between 2 LocalTime objects? LocalTime two = new LocalTime(2,0); LocalTime six = new LocalTime(6,0) So the number of milliseconds between 2am a

I am attending a Coursera class, and I am trying to do my homeworks. We have to write an SML program that takes a list of cards (caracterised by their suit and rank) and returns true if they all have

I have the following beginning of a function, and am unsure as to how I should return Middle Number (i.e. the number that is neither the largest nor smallest): middleNumber :: Int -> Int -> Int

For instance: template <typename Type1, typename Type2> void fun(const Type1 &v1, const Type2 &v2) { largest<Type1, Type2>::type val = v1 + v2; . . . }; I'd like to know if there

How do I get a list of MediaWiki namespaces? Ideally with name and number.

I am putting together a Forum Stats website and I need to find the number of Active Members on several forums. Many have Total members listed but that doesn't help me. I'm considering Active as

datatype term = node of string*term list | vnode of string i have a value of type term. How do i print it in sml to standard output.

What is the minimum number of comparisons required to find the largest and smallest elements of an unsorted list of n distinct elements? What could be the best time complexity for above algorithm? Fr

var myday= $('.tranche4').next().find(.fc-day-number).text(); Returns all the numbers on the calendar, how do I get just the day number on day cell where I double clicked?

I am trying to write a binary search that takes a sorted list and finds the largest number less than a target value: def binary_max(list, target) hi=len(list)-1 lo=0 while lo<=hi: mid=(hi+lo)//2 mi

This is a small piece of code that I am writing for an chemistry ab initio program. I am having issues making the C1pos list a number with exactly 6 digits after the decimal place. I have tried severa

Could someone tell me how I can find the largest table in a web page (i.e. the one with the most rows) using Nokogiri? Can this be done using Lambda functions?

I have spent a lot of time today trying to work out how I can get the number of reviews I have done on google plus. Ideally I would also love to get a list of the content for the actual reviews too.

Is there something like list pattern matching in SML/NJ, but for strings? What I want to do eventually is to remove the first character of a string, if it's a specific one, and a solution of this kind

I'm just practicing some MIT java assignments. But, I'm not sure how to find the second largest number. http://ocw.csail.mit.edu/f/13 public class Marathon { public static void main(String[] argument

I am asked to determine the largest fibonacci number that can be displayed on my system and I am wondering about how to do that.. here's my simple application that determines the nth fibonacci number

I'm working on a Project Euler problem which requires factorization of an integer. I can come up with a list of all of the primes that are the factor of a given number. The Fundamental Theorem of Arit

In SML I have created three infinite lists namely fibonacci, evenfib and oddfib. Now what I want to do is create a fourth list which will contain the first 10 numbers of evenfib and the first 10 numbe

Image I have a list L like L = a, b, c, d, e {3, 4, 5, 2, 1} I want to select the top 2 or 3 largest value from the list. For instance, I want top 3 from the list, that means I want c,

So I can easily accomplish task to find largest number and then if can be divided by three, print out. But do not know how to find second largest number from users sequence. Thanks for any hints! publ

Hello I'm trying to find the largest value in ma hash, I made a search in google and i found this code def largest_hash_key(hash) key = hash.sort{|a,b| a[1] <=> b[1]}.last puts key end hash = {

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

I have anywhere from 5 to 10 generic list in an ASP.NET VB.NET web app. I would like to write a method to pass them all into, and return only the elements they all have in common. I'm looking for some

if we have n lists, we need to select a number from each list, the selected number cannot be selected again, how to make selection to get the largest sum of n selected numbers? e.g. list1: 4 5 7. list

How would you set a variable to equal infinity (or any guaranteed largest number value) in C?

fib = [0,1] a = 1 b = 0 i = 0 while i < n: i = a+b a,b = i, a fib.append(i) This works in cases where 'n' (which is a given variable) is a number in an actual Fibonacci sequence, like 21 or 13. Ho

How do I include the mosml -P full into Run in command textmate for SML? and is it possible to have a live terminal window within textmate to test bits of code sort of like in emacs? thank you!

I want to use sml-mode for Emacs! So I installed emacs-24.2-bin-i386 everything is ok, i can see emacs and can run it) smlnj.msi when I try (run-->sml & type:1+1; => val it=2:int) it's ok

I am trying to find the n largest numbers in a particular column in SQL Server. We can find the largest value in a column and the 2nd largest value easily. But how do I find say, 5 largest values in a

I have a PyQt4 application with a QGridLayout as Layout. This layout has n widgets in it, each on another row, but not on another column. I have made all the widgets using a constructor. I was wonderi

I currently have an svn respository checked out to my local machine. How do I find the source URL that my changes are being checked into? (The URL of the actual repository). Running Linux Ubuntu 11.10

I have this question: Given two sorted lists (stored in arrays) of size n, find an O(log n) algorithm that computes the nth largest element in the union of the two lists. I can see there is probably

I Have Two Lists with User Defined Types e.g. List<User_Master> and List<User_Master_Temp> both the User_Master and User_Master_Temp contains the same type of variables with same name. how

I would like to make a program which allows you to enter a number (say 145). It reads the 3 integers and prints the largest one. int a, b, c, max; cout << Enter a, b and c: ; cin >> a &g

I heard there were some std functions that do give the largest n integers of an array, but how about a linked list? I would think a solution would be to have a few for loops to iterate over the linke

how to find the number of nodes in a loop of linked list? for e.g A ----> B ----> C -----> D -----> E Λ | | | | V H <----- G <----- F Find the number of nodes in a loop from C to H

I would like to sort my list of variables, from largest to smallest, and then print out the names of the variables. I have already tried Arrays, but when printing the array out, it prints out the valu

I have two models, Post hasMany Comment. How do I select all Post that have less than two Comment? I tried using a find with 'fields'=>array('COUNT(Comment.id) as numComments','Post.*'), (and then

I have this bit of code: fun foldr2(f, x::xs) = if xs = [] then x else f(x, foldr2(f, xs)) With the type signature (''a * ''a -> ''a) * ''a list -> ''a Looks pretty straight-forward, it takes

I'm trying to find the most occurring number in a tuple and assign that value to a variable. I tried the following code, but it gives me the frequency and the mode, when I only need the mode. from col