在这种情况下如何停止递归函数（SML）

Question

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

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

由于每次我都将第一个数字附加到末尾，所以如果 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

让我展示一些更多的实现变体。首先我们定义一个辅助函数，将一个list向左旋转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

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

我们已经计算出给定列表的长度使其旋转"copies"，但我们不必事先遍历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 函数的第二个参数是我们的 "accumulator"，它在这里表示为当前（部分）结果的对，如以前的实现和当前的旋转列表。这解释了 (List.rev o #1) 部分：我们需要获取累加器的第一个组件并将其反转。至于 ([], xs) 部分——当前结果一开始是空的（因此 []），我们开始旋转初始的 xs 列表。此外，(_, (res, rot)) 中的 _ 表示给定 xs 的当前元素，我们不关心它，因为它只是用作计数器（参见上一个变体）。

注意：o代表标准ML中的函数组合。

在这种情况下如何停止递归函数（SML）

how to stop a recursive function in this case (SML)

sml

smlnj

ml