如何在SML中找到列表中的最大数字

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

我们希望在给定的非空整数列表中找到最大的值。然后我们要比较列表中的元素。由于数据值是作为序列给出的，所以我们可以从列表的开头或结尾进行比较。定义在两个方面。a)从开始的比较b)从结束的比较(当数据值在列表中时，我们怎么做呢?)

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

5 个解决方案

#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.

在函数中，对列表的前两个元素进行比较，并将较大的值与其余的元素进行比较。我认为最后的比较意味着你要先找出列表尾部的最大数目，然后再与head元素进行比较。

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.

虽然这不是必需的，但是您应该处理空列表的情况，以确保完整性。用max函数可以缩短函数。

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.

说实话，我更喜欢你的版本，它是尾部递归的(它不会在大列表上乱堆)。我的函数可以重写为尾部递归，正如其他答案所示，但它肯定比函数更复杂。

#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.

正如@pad在他的代码中所演示的，应该应用的逻辑是进行递归调用，在解决函数当前范围的问题之前递归地解决子问题。

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:

在large的例子中，实际上没有必要逆向求解，因为它只需要使用更多的堆栈空间，这在“手工”执行代码时变得很明显。然而，设计模式在其他情况下是有用的。想象一个叫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:

手工运行“from the end”—最大的一个，假设每个缩进级别都需要在堆栈内存中保存函数调用的当前上下文，调用一个新函数并在~>箭头之后返回结果，可能会是这样的:

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:

那么，为什么这些非尾部递归函数在使用更多内存时，会使早期递归调用有用呢?如果我们回到unzip我们想要解决它而不需要这个烦人的"反向思考"我们有一个问题构造一个新的结果，这是一个元组，因为我们没有地方放置x和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:

创建这样一个位置的一个想法是创建一个辅助函数(helper函数)，该函数具有一些用于构建xs和ys的额外函数参数。当到达xys列表的末尾时，返回这些值:

(* 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:

但是你可能已经意识到这些(xs, ys)最终会反过来。解决这个问题的一个快速方法是在它们上使用rev，只有一次，在基本情况下最好实现:

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

这引出了一个有趣的问题:rev是如何实现的?

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

#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)));

#5

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

您还可以调整代码，例如在插入函数中传递匿名函数……