时间戳

首页 > 解决方案 > 如果此代码具有基本情况，为什么它会在 SML 中生成无限递归？

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

问题描述

我使用 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是[]，则辅助函数返回SOME accumulator

有谁能够帮我？

提前致谢。

标签： recursionsmlsmlnjinfinite-recursion

解决方案

正如@kopecs 指出的那样，这是由case xs ofwhen you want引起的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，因为它遵循一元设计模式。

推荐阅读