让 SML NJ 中的 val 声明

Question

我在理解它的工作原理时遇到了心理障碍，希望能得到一些指导。下面的函数 f 将对整数列表 (f [1,2,3]) 进行排序。我坚持的部分是 val 声明和递归中发生的事情。我知道 val 声明将允许我将列表中的第二个值与第一个值进行比较，但我对列表连接感到困惑。似乎该函数只会比较前两个值，然后添加到列表的其余部分（即 x :: y :: ys）。我不确定 f ls 实际上是如何工作的。难道是...

1) 比较前两个值并添加到列表中

2) 那么f ls被递归调用了？

似乎是这样，但后来我对 "ys" 感到困惑 - 似乎每次调用都会附加到列表的末尾。我知道排序有效，但不确定它实际如何工作。

fun f ([x]) = [x]
|   f(x :: ls) =

let 
    val (y :: ys) = f ls
in
    if y > x then x :: y :: ys
    else
        y :: x :: ys
end

EDIT - 再想一想，in / end 体内的 y::ys 实际上是递归调用的吗？如果是这样，SML 足够聪明，知道它应该在 y::ys 处使用 x::ys 如果它命中 else?

Answer 1

首先，当列表非常随机时，排序不起作用，例如f [2,3,4,1,2,4,6,0,6,7]

其次，要回答您关于此特定功能如何工作的问题，您可以通过在代码中添加以下 print 来轻松地将其可视化：

fun f ([x]) = [x]
|   f(x :: ls) = (print( (Int.toString (x)) ^ "\n");

let 
    val (y :: ys) = f ls
    val x_str = Int.toString (x)
    val y_str = Int.toString (y)
    val ys_str = concat (map Int.toString ys);
    val y_gt_x = if y > x then " ---> this one applies " else ""
    val x_gt_y = if x >= y then " ---> this one applies " else ""
in
    (print ("if " ^ y_str ^ " > " ^ x_str ^ 
            "\n      then " ^ x_str ^ " :: " ^ y_str ^ ys_str ^ y_gt_x ^ 
            "\n      else " ^ y_str ^ " :: " ^ x_str ^ ys_str ^  x_gt_y ^ "\n");
    if y > x then x :: y :: ys
    else
        y :: x :: ys)
end)

上面的随机列表输出如下：

- f [2,3,4,1,2,4,6,0,6,7];
2
3
4
1
2
4
6
0
6
if 7 > 6
      then 6 :: 7 ---> this one applies
      else 7 :: 6
if 6 > 0
      then 0 :: 67 ---> this one applies
      else 6 :: 07
if 0 > 6
      then 6 :: 067
      else 0 :: 667 ---> this one applies
if 0 > 4
      then 4 :: 0667
      else 0 :: 4667 ---> this one applies
if 0 > 2
      then 2 :: 04667
      else 0 :: 24667 ---> this one applies
if 0 > 1
      then 1 :: 024667
      else 0 :: 124667 ---> this one applies
if 0 > 4
      then 4 :: 0124667
      else 0 :: 4124667 ---> this one applies
if 0 > 3
      then 3 :: 04124667
      else 0 :: 34124667 ---> this one applies
if 0 > 2
      then 2 :: 034124667
      else 0 :: 234124667 ---> this one applies
val it = [0,2,3,4,1,2,4,6,6,7] : int list
-

如您所见，函数f在let绑定部分递归调用自身。（检查代码： let val (y :: ys) = f ls

如你所见，f ls是函数f的递归调用，所以你分析y :: ys是in体内的递归调用是不正确，因为这只是将元素 y 添加到列表 ys)

之前的操作

in 主体不会得到评估，除非一直在列表末尾。所以 in 主体将首先评估列表的最后两个元素，例如7 > 6 并相应地增加列表 ys。

第三，要回答为什么排序函数 f 不能正常工作的第一点，是因为它一直在向 ys 添加新元素，而没有查看是否放置了新元素对于其余元素，按 ys 顺序排列。是的，列表 ys 的第一个元素与要添加的新元素进行比较，因此两者中最大的元素将首先添加到 ys 的其余部分，但这并不能保证关于 ys.

的第二个和第三个等元素的正确放置

让 SML NJ 中的 val 声明

let val declarations in SML NJ

smlnj