让VAL在SML中的声明NJ

Question

我在理解这是如何工作的，并希望我能得到一些指导方面有一个心理障碍。下面的函数f将对整数列表（f [1,2,3]）进行排序。我坚持的部分是val声明和递归中发生的事情。我知道val声明将允许我将列表中的第二个值与第一个值进行比较，但是我对列表串联感到困惑。看起来这个函数只是比较前两个值，然后粘贴列表的其余部分（即x :: y :: ys）。我不确定如何实际工作。难道......

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 

编辑 - 想到这个多一些，难道是在中/结束体内y::ys实际上现在被称为递归？如果是这样，SML是足够聪明的知道它应该使用x::ys在y::ys的地方，如果它命中其他？

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。