1

这个函数找到一个列表的最大数量，我很难理解它：

fun max1 (xs : int list) = 
if null xs
    then NONE
        else 
            let val tl_ans =  max1(tl xs)
        in 
            if isSome tl_ans andalso valOf tl_ans > hd xs
                then 
                    tl_ans
                else 
                    SOME (hd xs)
end;

由于尚未设置，如何tl_ans在线计算？if isSome tl_ans andalso valOf tl_ans > hd xs

4

3 回答 3

3

该函数有两种情况：

1) 基本情况 - 列表为空 没有最大值，返回NONE

2) 列表不为空 - 由于列表不为空，列表将有一个头（第一个元素）和一个尾（除第一个元素之外的所有元素）。请注意，对于具有一个元素的列表，尾部将为空。

这里的想法是，对于非空列表，tl_ans在函数中递归地计算列表尾部的最大值（“尾部答案”或尾部中的最大值）。由于我们知道除了第一个元素（头）之外的所有元素中的最大值，现在整个列表的最大值就是列表中的最大值tl_ans和头。

在每次递归调用中，输入大小减少 1，因为我们只是传递列表的尾部（即没有第一个元素）。当它得到一个只有一个尾为空的元素的列表时，这最终将调用基本情况。从那里，在从每个递归调用返回的路上，该递归调用的头部将与递归返回的头部进行比较。

这是一个插图：

最大 [5,2,6,4]

tl_ans = max [2,6,4], hd = 5
         |
         |=>tl_ans = max [6,4], hd = 2
                   |
                   |=>tl_ans = max [4], hd = 6
                               |
                               |=>tl_ans = max [], hd = 4
                                           |
                                           |<= None (Base case)

                                <= Some 4, comparing tl_ans (None) and hd (4)
                    <== Some 6, comparing tl_ans (Some 4) and hd (6)
        <= Some 6, comparing tl_ans (Some 6) and hd (2)
<= Some 6, comparing tl_ans (some 6) and hd (5)
于 2013-09-13T03:55:58.893 回答
2

这不是在标准 ML 中编写此类函数的最惯用方式。我建议以另一种方式编写它，可以更好地理解它是如何工作的。函数valOf,hd和tl是所谓的部分函数，​​使用它们的唯一借口是确保它们的输入不是NONE或[]分别（在这种情况下程序将调用异常）。

使用valOf, hdortail将因此要求您检查列表是否为空（例如null xs）或选项是否存在（例如isSome ans），因此使用它的便利性受到限制。相反，需要使用模式匹配（或更强大的这些功能版本）。

下面我以另外两种方式编写了相同的函数，其中一种类似于您提供的那种。

(* For a list with at least one element in it, check to see if there is a
 * greatest element in the tail (xs). If there isn't, then x is the greatest
 * element. Otherwise, whichever is the greatest of x and y is the greatest.
 *
 * This solution is comparable to the one you have above: Find a solution
 * for the "smaller" problem (i.e. the reduced list in which x isn't in),
 * and then combine the solution. This means making a recursive call to a
 * function that doesn't exist at the time of writing it. *)
fun max [] = NONE
  | max (x::xs) =
    (case max xs of
         NONE   => SOME x
       | SOME y => SOME (Int.max (x, y)))

(* If we were to use a let-expression instead of a case-of, but still restrict
 * ourselves from using partial functions, we might make a helper function: *)
fun maxOpt (x, NONE) = SOME x
  | maxOpt (x, SOME y) = SOME (Int.max (x, y))

(* Now the essence of the let-expression is boiled down: It finds the largest
 * value in the tail, xs, and if it exists, finds the largest of that and x,
 * and pass it as a result packed in SOME. *)
fun max [] = NONE
  | max (x::xs) =
    let val y_opt = max xs
    in maxOpt (x, y_opt) end

(* In fact, one can store the largest value so far in the front of the list.
 * This is only because the return type is int option, and the input type is
 * int list. If the return type were dramatically different, it might not be
 * so easy. *)
fun max [] = NONE
  | max (x::y::xs) = max (Int.max (x,y)::xs)
  | max [x] = SOME x
于 2013-09-13T13:29:40.740 回答
2

线条

let val tl_ans =  max1(tl xs)
in 
    if isSome tl_ans andalso valOf tl_ans > hd xs

意思是让be的值在下面的代码中。 （你通常说的值绑定到名称（或变量）“tl_ans”。）tl_ansmax1 (tl xs)
max1 (tl xs)

意思是完全一样的

if isSome (max1 (tl xs)) andalso valOf (max1 (tl xs)) > hd xs

除了该值max1 (tl xs)只计算一次。

于 2013-09-13T06:39:46.017 回答