如何在这种情况下停止递归函数(SML)

Question

fun p(L) =
[L] @ p( tl(L) @ [hd(L)] );

如果L是[1，2，3]，那么我想要一个[[1,2,3]，[2,3,1]，[3,1,2]]。

因为每次我把第一个num附加到末尾，那么如果L=[]，那么[]在这里就不起作用。

一旦函数有了这三个列表，如何停止它？

Answer 1

函数中可以有一个参数x来跟踪递归的深度。

fun p(L, x) =
if x < length(L) then [L] @ p(tl(L) @ [hd(L)], x+1)
else [];

然后调用x=0的函数。

p([1, 2, 3], 0)

如果你不喜欢这个额外的参数，那么正如你可能知道的那样，你可以定义另一个函数，并使其等于参数强制为0的p函数。

fun p0(L) = p(L, 0);
p0([1, 2, 3]); (* same result as p([1, 2, 3], 0); *)

Answer 2

让我展示更多的实现变体。首先，让我们定义一个辅助函数，它将列表1的位置向左旋转：

(* operates on non-empty lists only *)
fun rot1_left (h :: tl) = tl @ [h]

那么p函数可以定义如下：

fun p xs =
let
(* returns reversed result *)
fun loop [] _ _   = []
| loop xs n res = 
if n = 0
then res
else loop (rot1_left xs) (n-1) (xs :: res)
in
List.rev (loop xs (length xs) [])
end

通常(性能方面)在列表的开头添加新元素，然后反转一次结果列表，比多次追加到末尾要好注意：这个版本在最后做了一个虚假的旋转，我本可以优化它，但没有，以使代码更清晰。

我们已经计算了给定列表的长度以使其旋转"副本"，但我们不必事先遍历xs，我们可以在旋转它的同时进行。因此，我们可以使用xs作为一种计数器，递归地调用xs列表尾部的loop助手函数。

fun p xs =
let
(* returns reversed result *)
fun loop [] _       _   = []
| loop xs []      res = res
| loop xs (_::tl) res = 
loop (rot1_left xs) tl (xs :: res)
in
List.rev (loop xs xs [])
end

这样，我们现在更接近于将p实现为foldl函数：

fun p xs =
(List.rev o #1)
(List.foldl
(fn (_, (res, rot)) => (rot::res, rot1_left rot))
([], xs)
xs)

List.foldl函数的第二个参数是我们的"累加器"，它在这里表示为当前(部分)结果的对，如在以前的实现中和当前旋转列表中。这解释了(List.rev o #1)部分：我们需要取累加器的第一个分量并将其反转。至于([], xs)部分，当前结果在开始时为空(因此为[])，我们开始旋转初始的xs列表。此外，(_, (res, rot))中的_表示给定xs的当前元素，我们不关心它，因为它只是用作计数器(请参阅上一个变体)。

注意：o代表标准ML中的功能组成。