SML中的尾遞歸不會出現任何輸出

Question

繼我之前的帖子here之後，我嘗試做了建議，並將代碼 轉換爲let的尾遞歸方法。

原始代碼 - 不工作（由於使用val內部if條件）：

fun func() = 

val decimal = 0 (* the final result *) 
val multiple = 0 (* keeps track of multiples, eg. In XXV, X would be a multiple *) 
val current = 0 (* the digit currently being processed *) 
val top = 0 (* value of the last element in the list *) 
val last_add = 0 (* the last digit that wasn't a multiple, or subtraction operation *) 
val last_sub = 0 
val problem = 0 (* if value is 1 then there is a problem with the input *) 
val myList = [1,2,3,4,5] (* the list has more values *) 

while (myList <> []) (* run while the list is not empty *) 

    val current = tl(myList) (* grab the last element from the list *) 
    val myList = tl(myList) (* remove the last element from the list *) 
    val top = tl(myList) (* grab the value at the end of the list *) 
    if (myList <> []) andalso (current > top)) 
     then  

       val decimal = decimal + current - top 
       val last_sub = top; 
       val myList = tl(myList) 
     else  
      if ((myList = []) andalso (current = top)) 
       then val decimal = decimal + current 
        val multiple = multiple + 1 
       else 
        if (last_sub = current) 
        then val problem = 1 

        else 
          val decimal = decimal + current 
          val multiple = 0 
          val last_add = current 

和代碼作爲尾遞歸方法：

fun calc [] = 0 
    |calc [x] = x 
    |calc (head::tail) = 
     let 
      val decimal = 0 
      val multiple = 0 
      val current = 0 
      val top = 0 
      val last_add = 0 
      val last_sub = 0 
      val problem = 0 
      val doNothing = 0 
     in  

      let 
       val current = hd(rev(head::tail)) (* grab the last element *) 
       val head::tail = rev(tl(rev(head::tail))) (* POP action - remove the last element from the list *) 
       val top = hd(rev(head::tail))  (* grab the new last element after removing *) 
       in 
       if (current > top) then 
        let 
          val decimal = decimal + current - top 
          val last_sub = top 
          val head::tail = rev(tl(rev(head::tail))) (* POP action - remove the last element from the list *) 
        in 
        calc(head::tail) 
        end 
       else 
       if ((head::tail = []) andalso (current = top)) 
        then let 
          val decimal = decimal + current 
          val multiple = multiple + 1 
         in 
          calc(head::tail) 
         end 
       else 
        if (last_sub <> current) 
         then let 
           val decimal = decimal + current 
           val multiple = 0 
           val last_add = current 
          in 
           calc(head::tail) 
          end 
        else 
         (* do nothing *)  
         val doNothing = 0 
       end  

     end; 

然而，當我嘗試輸入時：

calc([0,100,20,30,4,50]); 

我得到：

uncaught exception Bind [nonexhaustive binding failure] 
    raised at: stdIn:216.13-216.50 

我知道代碼是非常難以閱讀和很長，但將不勝感激 如果有人能向我解釋如何解決它，或者幫助我找到原因這個輸出。

謝謝

Answer 1

您的代碼存在一些問題。

首先，您可以使用last來獲取列表的最後一個元素。有關更多信息，請參閱List documentation。但是，除非你有充分的理由這樣做，否則從列表開始處簡單地開始並在開始時將元素從頭開始放置會更容易和更有效。您的代碼中已使用模式匹配將第一個元素綁定到head。其次，除非您使用ref（您可能不想這麼做），Standard ML中只有值沒有變量。這意味着如果你想在調用之間進行狀態轉移，任何累加器都需要成爲你的函數的參數。使用輔助函數來初始化累加器是一種常見模式。

第三，不要將列表與[]進行比較來測試它是否爲空，請使用null函數。請相信我。由於微妙的類型推斷問題，您會收到使用=的警告。更好的是，在函數的參數上使用模式匹配，或者使用case語句。模式匹配允許編譯器告訴你是否處理了所有可能的情況。

第四，SML通常對變量名稱使用camelCase而不是snake_case。這更具風格，但是當你編寫更多的代碼和協作時，你會想要符合這些約定。

第五，當您在列表上進行遞歸時，不要嘗試查看列表中的多個值。這使事情變得複雜。把它當作頭元素和尾單，一切都會變得簡單多了。在我的代碼中，我沒有將列表保存在當前列表中，而是通過將其拆分爲單獨的參數來完成此操作。有一個簡單的例子，您只需從一個累加器返回答案，然後使用一個遞歸的情況下遞歸更新的累加器值和從列表中彈出的單個值。這消除了這個問題。

我不確定這個邏輯是否正確，因爲我不知道你在計算什麼，但看看這段代碼說明了我所談論的一些事情。

(* This is the helper function which takes accumulators as 
    parameters. You shouldn't call this directly. *) 
fun calc' decimal _ _ _ _ [] = 
    (* We processed everything in the list. Just return the accumulator. *) 
    decimal 
    | calc' decimal multiple lastAdd lastSub current (top::tail) = 
    (* This case is for when there are 1 or more elements in the list. *) 
    if current > top then 
     calc' (decimal + current - top) multiple lastAdd top top tail 
    else if current = top then 
     calc' (decimal + current) (multiple + 1) lastAdd lastSub top tail 
    else 
     calc' (decimal + current) 0 current lastSub top tail 

(* This is the function you should call. *) 
fun calc [] = 0 
    | calc [_] = 0 (* Given a single-element list. *) 
    | calc (x::xs) = 
    (* Apply the helper with correct initial values. *) 
    calc' 0 0 0 0 x xs 

在功能性語言，而不是當你想改變它，只是重複並指定正確的參數的新值賦值給一個變量。這就是你如何使用遞歸在函數式語言中編寫一個「循環」。只要你只使用尾遞歸，它就和你最喜歡的命令式語言中的while循環一樣高效。