讓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。