如果此代码具有基本情况，为什么它会在 SML 中生成无限递归？

Question

我使用 NJ 编译器在 SML 中编写了以下代码：

fun all_answers (f, xs) = 
    let 
        fun aux(accu, xs_left) = 
            case xs of
               [] => SOME accu
            | x::xs' => case f(x) of 
                          NONE => NONE
                        | SOME y => aux(accu@y, xs')
    in
        aux([], xs)
    end

它很适合这个测试：

val testAll1 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), []) = SOME []
val testAll2 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), [2,3,4,5,6,7]) = NONE

但是，这个测试发生了一些奇怪的事情：

val testAll3 = all_answers ((fn x => if x = 1 then SOME [x] else NONE), [1]) = SOME [1]

在运行程序之后，终端将永远运行。

我定义了尾递归并使用模式匹配 xs' 到达尾部。

此外，我定义了基本情况来结束递归，这样如果 xs 是 [] 那么辅助函数 returns SOME accumulator

有人可以帮我吗？

提前致谢。

Answer 1

正如@kopecs 所指出的，这是由 case xs of 当你想要 case xs_left of.

引起的

这是您的函数的清理（空白、命名）版本：

fun all_answers (f, ys) =
    let
        fun aux (accu, xs) =
            case xs of
                 [] => SOME accu
               | x::xs' => case f x of
                                NONE => NONE
                              | SOME y => aux (accu@y, xs)
    in
        aux ([], ys)
    end

您至少可以做两件事来简化此函数的创建方式。 (1) 在函数模式中执行 case xs of 而不是在嵌套的 case-of 中。 (2) 删除内部 aux 函数并简单地在外部函数中进行递归，代价是一些尾递归

第一个简化可能如下所示：

fun all_answers2 (f, ys) =
    let
        fun aux (accu, []) = SOME accu
          | aux (accu, x::xs) =
               case f x of
                    NONE => NONE
                  | SOME y => aux (accu@y, xs)
    in
        aux ([], ys)
    end

第二个可能看起来像：

fun all_answers' (f, []) = SOME []
  | all_answers' (f, x::xs) =
      case f x of
           NONE => NONE
         | SOME ys => case all_answers' (f, xs) of
                           NONE => NONE
                         | SOME result => SOME (ys @ result)

这显示了一个模式：每当你有

case f x of
     NONE => NONE
   | SOME y => case g y of
                    NONE => NONE
                  | SOME z => ...

然后你就有了一个可以用函数抽象出来的编程模式。

已经有一个标准库函数是为此而创建的，叫做 Option.map，所以你可以这样写：

fun all_answers3 (f, ys) =
    let
        fun aux (accu, []) = SOME accu
          | aux (accu, x::xs) =
              Option.map (fn y => aux (accu@y, xs))
                         (f x)
    in
        aux ([], ys)
    end

尝试在 REPL 中使用这个函数：

- Option.map (fn y => y + 2) NONE;
> val it = NONE : int option
- Option.map (fn y => y + 2) (SOME 2);
> val it = SOME 4 : int option

从另一个方向来看，而不是内部功能：

(* Alternative to Option.map: *)
fun for NONE _ = NONE
  | for (SOME x) f = f x

(* Equivalent to Option.mapPartial with "flipped" arguments: *)
fun for opt f = Option.mapPartial f opt

fun all_answers'' (f, []) = SOME []
  | all_answers'' (f, x::xs) =
      for (f x) (fn ys =>
        for (all_answers'' (f, xs)) (fn result =>
          SOME (ys @ result)))

这种风格更像 Haskell 因为它遵循单子设计模式。

如果此代码具有基本情况，为什么它会在 SML 中生成无限递归？

Why is this code is generating an infinite recursion in SML if it has a base case?

recursion

sml

smlnj

infinite-recursion