标准ML递归函数误差

Question

所以我刚开始使用ML编程，我在一本书中找到了这个摘录。摘录要求构建一个接受整数和列表的递归函数。如果L=a1，a2，a3，则所需的结果是ai+1，ai+2，.，an，a1，a2，…，ai。所以我写了一个函数，很多小时后，我把错误缩小到一个我无法理解的错误。这是我的功能：

fun cycle L i = 
    if i = 0 then L
    else (cycle tl(L) (i-1)) @ [hd(L)];

我会上传一张带有错误的图片，这样就可以有人向我解释翻译想对我说什么。

​

​

"a“旁边的数字只显示list.So for L=1,2,3,4,5中这些元素的顺序，对于i= 2，所期望的结果是List L=3,4,5,1,2，我不认为列表的类型在这个问题中是必要的。希望这个进一步的解释能有所帮助

Answer 1

这是递归调用cycle tl(L) (i-1)的语法问题。

在SML中，函数应用程序的语法是并置，而不是括号。在您的例子中，tl(L)确实用参数L调用函数tl，但这等同于tl L。括号是多余的，因此被忽略。

现在，如果您在原始调用中替换最小版本，您将得到以下内容：cycle tl L (i-1)。它使用三个参数调用cycle，而不是只调用两个参数。

正确的写作方式应该是：cycle (tl L) (i-1)。

Answer 2

Ionuț已经对语法问题给出了足够的答案；下面是一些进一步的建议：

1. 使用模式匹配而不是hd和tl。
2. 考虑一下基本情况；您能想到的最简单的子问题是什么？例如，循环空列表总是会给出空列表而不管n，而循环L0次总是会返回L。将这两个基本案例作为模式是有帮助的。
3. 考虑递归的情况；顶部元素(假设它存在)被循环，我被减少一个，直到最终我是0或者L是空的。因为第二个基本情况捕获空列表，所以我们可以自由地假设L在这里是非空的，在这种情况下，它将匹配模式x::xs。 有趣的周期0 xs = xs收环i [] = [] xs循环i (x::xs) =循环(i-1) (xs @ x)
4. 根据0 <= i和i <= length xs是否是函数的先决条件，您可能希望在激活主递归之前处理这些条件一次，例如，将上面的函数包装起来： 如果0 <= i和i <=长度xs，则i [] = []循环‘i (x:: xs ) =循环’(i-1) (xs @ x)，则循环‘i’的长度为xs。
5. 主要操作，即xs @ [x]，效率非常低，因为它的运行时间与xs的长度成正比，并且被激活了n次。因此，当像O(min(n，x，x，L))这样的事情应该是可以实现的时候，cycle的运行时间就变成了O(n . 如果在不使用@的情况下将循环元素存储在单独的列表中，并且在元素被循环之后将其余元素与此列表组合起来，您可能会制作一个更快的版本。根据您对0 <= i和i <= length xs的感受，您可能会遇到以下测试用例的问题： val cycle_test_1 =(周期5 1,2,3,4 = 2,3,4,1)