标准 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 中这些元素的顺序，对于 L=[1,2,3,4,5] 和 i = 2，期望的结果是列表 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ţ 已经对语法问题给出了充分的答案；这里有一些进一步的建议：

使用模式匹配而不是hd和tl。
考虑基本情况；你能想到的最简单的子问题是什么？例如。无论n如何，循环空列表总是会给出空列表，而循环L 0次总是会给出L 回来。将两种基本情况作为模式会有所帮助。
考虑递归的情况；顶部元素（假设它存在）被循环并且 i 减一，直到最终 i 为 0 或 L 为空。因为第二个基本情况捕获了空列表，我们可以自由地假设 L 在这里是非空的，在这种情况下它将匹配模式 x::xs.
```
fun cycle 0 xs = xs
  | cycle i [] = []
  | cycle i (x::xs) = cycle (i-1) (xs @ [x])
```

根据 0 <= i 和 i <= length xs 是否是函数的先决条件，您可能希望在激活主递归之前处理一次，例如通过包装上面的函数：

fun cycle i ys =
    let fun fun cycle' 0 xs = xs
              | cycle' i [] = []
              | cycle' i (x::xs) = cycle' (i-1) (xs @ [x])
    in
      if 0 <= i andalso i <= length xs
      then cycle' i ys
      else raise Domain
    end

主操作，即xs @ [x]效率极低，因为它的运行ning时间与xs的长度成正比，被激活n 次。所以 cycle 的运行ning 时间变成 O(n • |L|) 当 O(min(n,|L |))应该是可以实现的。

如果您将循环元素存储在单独的列表中而不使用 @，并在元素循环后将剩余元素与该列表组合，您可能会制作一个更快的版本。根据您对 0 <= i 和 i <= length xs 的看法，您可能运行遇到以下测试用例的问题：
```
val cycle_test_1 = (cycle 5 [1,2,3,4] = [2,3,4,1])
```

标准 ML 递归函数错误

Standard ML recursive function error

sml