loops - SML - 列表替换函数的迭代翻译

Question

我相信我在将第一个函数转换为仅使用赋值和循环方面处于正确的轨道上。我知道这违背了函数式编程，但这正是教授想要的。

递归函数:

fun sub (x, y, []) = []
  | sub (x, y, z::zz) = if x = z then y::sub(x, y, zz)
            else z::sub(x, y, zz);

迭代翻译:

fun sub2 (x, y, z) =
    let val ret = ref []; val temp = z;
    in
        while !temp <> []
        do (if x = hd(!temp) then ret := !ret::y; temp := tl(!temp)
            else ret := ret::hd(!temp); temp := tl(!temp));
        !ret;
    end;

我在 smlnj 上运行时收到以下错误。第一个与 do 放在同一行，第二个在末尾。

Error: syntax error: replacing END with EQUALOP

Error: syntax error found at EOF

我希望能够帮助调试或者以更简洁的方式来完成此迭代功能。

Answer 1

为什么哦为什么他不想那样呢？没关系...

存在不少问题。

1. 您在不需要的地方使用了很多分号。但这不是语法错误。
2. 您忘记了 if 语句中的序列 (exp1; exp2) 周围的括号。只允许在 let..in..end 表达式的“in”部分排除括号。
3. 您将 temp 作为引用类型进行引用(使用 := 和 !)。然而，您还没有将其设为引用。这意味着您的输入变量 z 必须作为引用给出。如果这是您想要的，那么它与原始子功能不匹配。
4. 原始子函数将其自身限制为相等类型。但是，如果情况并非如此，那么您的!temp <> null会做出限制。使用List.null将是“最佳实践”而是使用函数。
5. 最后的分号!ret;当你的序列停止时不应该在那里，否则 end将成为失败序列的一部分。
6. 您忘记取消引用 ret在你的其他部分条件中。
7. 您已切换 cons (::) 的参数。缺点有类型 'a * 'a list因此需要一个元素，然后是一个元素列表。解决此问题并仍然保留元素顺序的一种方法是使用追加 (@) 函数，然后将要追加的元素放置在单例列表中。然而，有很多方法可以更好地处理这个问题，因为追加函数在大列表上表现非常差。

以下是一个有效的函数:

fun sub2 (x, y, z) =
let 
  val ret = ref []
  val temp = ref z
in
  while not (null (!temp)) do 
    if x = hd(!temp) then 
      (ret := !ret @ [y]; 
       temp := tl(!temp))
    else 
      (ret := !ret @ [hd(!temp)]; 
       temp := tl (!temp));
  !ret
end

这里可以改进的一个明显的事情是您始终使用相同的值更新 temp。所以这个可以排除掉。并且条件可以改为案例

fun sub2 (x, y, z) =
    let 
      val ret = ref []
      val temp = ref z
    in
      while not (null (!temp)) do       
        (case x = hd(!temp) of
          true => ret := y :: !ret
        | false => ret := hd(!temp) :: !ret
       ;temp := tl (!temp));         
      rev (!ret)
    end

特别注意元素不是附加到结果列表中，而是放在前面，然后在最后将结果列表反转以获得正确的顺序。这将使您在大型列表上获得更好的性能。然而，当您在 SML 中采用命令式风格时，还有更好的方法可以做到这一点。

正如您已经看到的，它可以通过函数式方式完成。但它也可以做得更简单。使用 map 考虑以下内容。

fun sub3 (x, y, zs) = map (fn z => if z = x then y else z) zs