更改爲尾遞歸SML

好吧，所以我試圖將此函數更改爲尾遞歸。我對Tail遞歸的定義是使用「本地幫助函數」來累積我的答案，並在不遞迴調用主函數的情況下返回它。更改爲尾遞歸SML

這些功能正常工作。

fun same_string(s1 : string, s2 : string) = 
s1 = s2 

fun all_except_option (name, []) = NONE 
    | all_except_option (name, x::xs)= 
case same_string (x , name) of 
true => SOME xs 
    | false => case all_except_option(name,xs) of 
     NONE => NONE 
      | SOME z => SOME(x::z) 

fun get_substitutions1 ([],name2) = [] (*get_substitutions2 is same but tail recursive *) 
    | get_substitutions1 (x::xs,name2) = 
    case all_except_option (name2,x) of 
     NONE => get_substitutions1 (xs,name2) 
     | SOME z => z @ get_substitutions1(xs,name2)

因此，這裏有我的企圖尾遞歸不工作，我想我失去了一些東西相當基本的，我俯瞰，由於我缺乏經驗SML。

fun get_substitutions2 (lst,name3) = 
let fun aux (xs,acc) = 
case all_except_option(name3,x::xs) of 
    NONE => aux(xs, acc) 
    | SOME z => aux(xs, z::acc) 
in 
aux(lst,[]) 
end

和

fun get_substitutions2 (lst,name3) = 
let fun aux (xs,acc) = 
case all_except_option(name3,x::xs) of 
    NONE => aux(xs, acc) 
    | SOME z => aux(xs, [email protected]) 
in 
aux(lst,[""]) 
end

兩個「get_substitutions」的功能都應該做同樣的事情。將String1與字符串列表list進行比較，返回由包含String1減去String1的所有列表組成的所有列表。

我嘗試使用尾遞歸導致以下錯誤。

Error: unbound variable or constructor: x 

uncaught exception Error 
    raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27 
      ../compiler/TopLevel/interact/evalloop.sml:44.55 
      ../compiler/TopLevel/interact/evalloop.sml:296.17-

這裏是調用get_substitutions2的幾個例子：

get_substitutions2 ([["foo"],["there"]], "foo"); (* = [] *) 
get_substitutions2 ([["fred","fredrick","freddie","F","freddy"],["Will","William","Willy","Bill"]],"Bill"); (* = ["Will","William","Willy"] *) 
get_substitutions2 ([["a","b"],["a","c"],["x","y"]], "a"); (* = ["c","b"] *)

來源

2013-10-21 user2865449

錯誤來了因爲（BIG SURPRISE！）'x'在你的函數中沒有綁定。你不要在任何地方定義'x'，所以編譯器不知道它是什麼。我想你只想'xs'，而不是'x :: xs'。但是，在花費大約10分鐘時間查看代碼後，我無法確切知道您想要做什麼，並且我不認爲您知道自己在做什麼。對於初學者來說，遞歸幫助函數「acc」缺少一個基本情況。你也應該知道你是否應該根據'z'的類型使用'@'（concatenate）或'::'（prepend），以及你想要的結果。 – DaoWen

感謝您的評論。你是對的，我對自己在做什麼一無所知，因爲我被賦予了極端的基礎知識，被要求用我不熟悉的語言編寫中間代碼。這就是我尋求幫助的原因。我很難解決x :: xs如何與hd xs同義，以及如何在函數get_substitutions1中看到的組合列表。 – user2865449

我不認爲這個語言與[範式]（http://en.wikipedia.org/wiki/Programming_paradigm）是一樣多的問題。你似乎並不熟悉很多函數式編程概念（遞歸，模式匹配，[cons-lists]（http://en.wikipedia.org/wiki/Cons#Lists）等）。你應該嘗試提出更具體的問題。你可能有更好的運氣在'＃sml @ irc.freenode.net'與人聊天，因爲實際上你可以以一種合適的速度進行討論，不像在stackoverflow上留下評論。 – DaoWen

您需要使用您已經爲get_substitutions1同樣的模式在aux函數定義：

fun get_substitutions2 (lst,name3) = 
let fun aux ([],acc) = acc (* BASE CASE *) 
     | aux (x::xs,acc) = (* BINDING x IN PATTERN *) 
case all_except_option(name3,x) of 
    NONE => aux(xs, acc) 
    | SOME z => aux(xs, [email protected]) 
in 
aux(lst,[]) 
end

來源

2013-10-21 04:24:04 DaoWen

我不認爲這是正確的。當我們改變尾部遞歸調用時，我們也需要改變追加順序。應該是'aux（xs，acc @ z）'而不是'aux（xs，z @ acc）' – yusong

更改爲尾遞歸SML

回答

相關問題