SML中的尾递归不提供任何输出 [英] Tail recursion in SML does not present any output
问题描述
继我的上一篇文章此处 ，我试着去做所建议的事情，并将代码
转换为一个Tail-recursion方法，其中 let 。
原始代码不起作用（由于在内使用 val > if 条件）：
fun func（）=
val decimal = 0（*最终结果*）
val multiple = 0（*记录倍数，例如在XXV中，X将是倍数*）
val当前值= 0（*当前正在处理的数字*）
val top = 0（*列表中最后一个元素的值*）
val last_add = 0（*不是多重或减法运算*的最后一位数字）
val last_sub = 0
val问题= 0（*如果值为1，那么输入存在问题*）
val myList = [1,2,3,4,5]（*列表中有更多值*）
while（myLis t< [*] $ * b
$ b val current = tl（myList）（*获取列表中的最后一个元素*）
val myList = tl（myList ）（*删除列表中的最后一个元素*）
val top = tl（myList）（*获取列表末尾的值*）
if（myList<> []） andalso（current> top））
then
val decimal = decimal + current - top
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 =当前
而代码作为尾部 - 递归方法：
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问题= 0
val doNothing = 0
in
let
val current = hd（rev（head :: tail））（*获取最后一个元素*）
val head :: tail = rev tl（rev（head :: tail）））（* POP action - 从列表中删除最后一个元素*）
val top = hd（rev（head :: tail））（*在
中删除*）
if（current>然后
让
val decimal = decimal + current - top
val last_sub = top
val head :: tail = rev（tl（rev（head :: tail）） ）（* POP action - 从列表中删除最后一个元素*）
in
calc（head :: tail）
end
else
if（（head： ：tail = []）andalso（current = top））
然后让
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 =当前
calc（head :: tail）
结束
else
（*什么都不做*）
val没有= 0
结束
结束;
然而，当我尝试输入时：
计算值（[0,100,20,30,4,50]）;
我得到：
未捕获的异常Bind [非穷举性绑定失败]
在：stdIn引发：216.13-216.50
我知道这段代码很难阅读并且很长，但是如果有人能够向我解释如何解决这个问题，或者帮我找到这个输出的原因，我会非常感激
。 / p>
谢谢 解决方案
您的代码存在一些问题。 / p>
首先，您可以使用 last 来获取列表的最后一个元素。有关更多信息，请参见列表文档。但是，除非你有充分的理由这样做，否则从列表开始处简单地开始并在开始时将元素从头开始放置会更容易和更有效。你已经有第一个元素绑定到使用模式匹配的代码中 head 。
ref s（你可能不想这样做），Standard ML中只有值没有变量。这意味着如果你想在调用之间进行状态转移，任何累加器都需要成为你的函数的参数。使用辅助函数来初始化累加器是一种常见的模式。第三，不是比较列表与 [] 要测试它是否为空，请使用 null 函数。请相信我。由于微妙的类型推断问题，您将使用 = 获取警告。更好的是，在函数的参数上使用模式匹配，或使用 case 语句。模式匹配允许编译器告诉你是否处理了所有可能的情况。 第四，SML通常对变量名使用camelCase而不是snake_case。这是更具风格的，但当你编写更多的代码和协作，你会想要符合约定。第五，当你在列表上进行递归时，不要试图查看列表中的多个值。这使事情变得复杂。把它当作头元素和尾单，一切都会变得简单多了。在我的代码中，我没有将列表保存在当前列表中，而是通过将其拆分为单独的参数来完成此操作。有一个简单的例子，您只需从一个累加器返回答案，然后使用一个递归的情况下递归更新的累加器值和从列表中弹出的单个值。这消除了这个问题。
我不确定这个逻辑是否正确，因为我不知道你在计算什么，但看看这段代码它说明了我谈到的一些事情。
（*这是辅助函数，它将累加器作为
参数。*）
fun calc'decimal _ _ _ _ [] =
（*我们处理了列表中的所有内容，只返回累加器。*）
十进制
| calc'decimal multiple lastAdd lastSub current（top :: tail）=
（*这种情况适用于列表中有一个或多个元素的情况*）
if current>然后
calc'（decimal + current - top）multiple lastAdd top top tail
else if if current = top then
calc'（decimal + current）（multiple + 1）lastAdd lastSub top tail
else
calc'（decimal + current）0 current lastSub top tail
（*这是您应该调用的函数*）
fun calc [] = 0
| calc [_] = 0（*给定一个单元素列表。*）
| calc（x :: xs）=
（*以正确的初始值应用助手*）
calc'0 0 0 0 x xs
在函数式语言中，当您想要更改变量时，不必为变量指定变量，只需简单地为正确的参数递归并指定新值即可。这就是你如何使用递归在函数式语言中编写一个循环。只要您只使用尾递归，它就会像您最喜欢的命令式语言中的while循环一样高效。
Following my previous post here , I tried to do what was suggested and convert the code
into a Tail-recursion method with let .
The original code - which does not work (due to using val inside if condition) :
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
And the code as a tail-recursion method :
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;
However , when I try to enter :
calc([0,100,20,30,4,50]);
I get :
uncaught exception Bind [nonexhaustive binding failure]
raised at: stdIn:216.13-216.50
I know the code is very hard to read and pretty long , but it would be greatly appreciated if someone could explain to me how to fix it , or help me find the reason for this output .
Thanks
You have a few issues with your code.
First of all, you can use last to grab the last element of a list. See the List documentation for more info. But unless you have a really good reason to do so, it's easier and much more efficient to simply start from the beginning of the list and pop elements off the beginning as you recurse. You already have the first element bound to head in your code using pattern matching.
Secondly, unless you use refs (which you probably don't want to do) there are no variables in Standard ML, only values. What this means is that if you want to carry state between invocations, any accumulators need to be parameters of your function. Using a helper function to initialize accumulators is a common pattern.
Third, instead of comparing a list to [] to test if it's empty, use the null function. Trust me on this. You'll get warnings using = because of subtle type inference issues. Better yet, use a pattern match on your function's parameters or use a case statement. Pattern matching allows the compiler to tell you whether you've handled all possible cases.
Fourth, SML typically uses camelCase, not snake_case, for variable names. This is more stylistic, but as you write more code and collaborate, you're going to want to fit with the conventions.
Fifth, when you do recursion on a list, don't try to look at multiple values in the list. This complicates things. Treat it as a head element and tail list, and everything will become much simpler. In my code, instead of keeping current in the list, I did this by splitting it out into a separate parameter. Have a base case where you simply return the answer from one of your accumulators, and a recursive case where you recurse with updated accumulator values and a single value popped from your list. This eliminates the problem scenario.
I'm not sure if this logic is correct since I don't know what you're trying to calculate, but check out this code which illustrates some of the things I talked about.
(* 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
In a functional language, instead of assigning to a variable when you want to change it, simply recurse and specify the new value for the correct parameter. This is how you write a "loop" in a functional language using recursion. As long as you only use tail-recursion, it will be just as efficient as a while loop in your favorite imperative language.
这篇关于SML中的尾递归不提供任何输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
