我们想在给定的非空整数列表中找到最大值。然后我们必须比较列表中的元素。由于数据值是作为序列给出的，我们可以从列表的开头或结尾进行比较。以两种方式定义。a) 从头比较 b) 从尾比较（当数据值在列表中时，我们如何做到这一点？）
我所做的是从一开始就通过比较找到最大的数字。
我怎么能从头到尾做到这一点？我应该应用什么逻辑？
这是我从一开始就进行比较的代码。
- 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
在您的函数中，比较列表的前两个元素，并将较大的值与其余元素进行比较。我认为从末尾进行比较意味着您首先尝试找到列表尾部的最大数量，然后将其与头部元素进行比较。
fun largest [] = raise Empty
| largest [x] = x
| largest (x::xs) =
let
val y = largest xs
in
if x > y then x else y
end
虽然不是必需的，但为了完整性，您应该处理空列表的情况。如果使用函数，你可以缩短max函数。
fun largest [] = raise Empty
| largest [x] = x
| largest (x::xs) = max(x, largest xs)
老实说，我更喜欢你的尾递归版本（它不会在大列表中破坏堆栈）。正如其他答案所示，我的函数可以重写为尾递归，但它肯定比你的函数更复杂。
正如@pad 用他的代码演示的那样，应该应用的逻辑是进行递归调用，在解决函数当前范围的问题之前递归地解决子问题。
在 的情况下largest，向后解决它实际上没有任何意义，因为它只是使用更多的堆栈空间，这在“手动”执行代码时变得很明显。然而，设计模式在其他情况下很有用。想象一个名为的函数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 _ = []
此函数将两个列表的元组转换为许多元组的列表，丢弃剩余值。它在某些情况下可能很有用，并且定义它也不是那么糟糕。然而，制作它的对应物 ，unzip有点棘手：
(* 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
手动运行常规“从头开始” - 最大可能如下所示：
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
手动运行“从头开始” - 最大，想象每个缩进级别都需要将函数调用的当前上下文保存在堆栈内存中，调用新函数并在~>箭头之后返回结果，可能如下所示：
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
那么，如果这些非尾递归函数只是使用更多内存，为什么它们会使早期递归调用有用呢？好吧，如果我们回过头来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...
制作这样一个地方的一个想法是创建一个辅助函数（辅助函数），它有一些额外的函数参数来构建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
但是您可能已经意识到，(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
这就引出了一个有趣的问题：如何rev实现？
(*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)));
我建议使用尾递归助手，它将当前最大值作为累加器传递。
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;
我知道现在回答您的问题为时已晚，但希望这会有所帮助：
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));
您还可以调整代码，例如在插入函数中传递匿名函数...